<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
    
    <title>SimpleDBM Developers’s Guide &mdash; SimpleDBM v1.0.12 BETA documentation</title>
    <link rel="stylesheet" href="_static/default.css" type="text/css" />
    <link rel="stylesheet" href="_static/pygments.css" type="text/css" />
    <script type="text/javascript">
      var DOCUMENTATION_OPTIONS = {
        URL_ROOT:    '#',
        VERSION:     '1.0.12 BETA',
        COLLAPSE_MODINDEX: false,
        FILE_SUFFIX: '.html',
        HAS_SOURCE:  true
      };
    </script>
    <script type="text/javascript" src="_static/jquery.js"></script>
    <script type="text/javascript" src="_static/doctools.js"></script>
    <link rel="top" title="SimpleDBM v1.0.12 BETA documentation" href="index.html" />
    <link rel="prev" title="SimpleDBM RSS User’s Manual" href="usermanual.html" /> 
  </head>
  <body>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="usermanual.html" title="SimpleDBM RSS User’s Manual"
             accesskey="P">previous</a></li>
        <li><a href="index.html">SimpleDBM v1.0.12 BETA documentation</a> &raquo;</li> 
      </ul>
    </div>  

    <div class="document">
      <div class="documentwrapper">
        <div class="bodywrapper">
          <div class="body">
            
  <div class="section" id="simpledbm-developers-s-guide">
<h1><a class="toc-backref" href="#id49">SimpleDBM Developers&#8217;s Guide</a><a class="headerlink" href="#simpledbm-developers-s-guide" title="Permalink to this headline">¶</a></h1>
<table class="docutils field-list" frame="void" rules="none">
<col class="field-name" />
<col class="field-body" />
<tbody valign="top">
<tr class="field"><th class="field-name">Author:</th><td class="field-body">Dibyendu Majumdar</td>
</tr>
<tr class="field"><th class="field-name">Contact:</th><td class="field-body">d dot majumdar at gmail dot com</td>
</tr>
<tr class="field"><th class="field-name">Date:</th><td class="field-body">7 April 2009</td>
</tr>
<tr class="field"><th class="field-name">Version:</th><td class="field-body">1.0.12</td>
</tr>
<tr class="field"><th class="field-name">Copyright:</th><td class="field-body">Copyright by Dibyendu Majumdar, 2005-2009</td>
</tr>
</tbody>
</table>
<div class="contents topic" id="contents">
<p class="topic-title first">Contents</p>
<ul class="simple">
<li><a class="reference internal" href="#simpledbm-developers-s-guide" id="id49">SimpleDBM Developers&#8217;s Guide</a><ul>
<li><a class="reference internal" href="#introduction" id="id50">Introduction</a><ul>
<li><a class="reference internal" href="#intended-audience" id="id51">Intended Audience</a></li>
<li><a class="reference internal" href="#pre-requisite-reading" id="id52">Pre-requisite Reading</a></li>
</ul>
</li>
<li><a class="reference internal" href="#data-manager-rss-components" id="id53">Data Manager/RSS Components</a></li>
<li><a class="reference internal" href="#object-registry" id="id54">Object Registry</a><ul>
<li><a class="reference internal" href="#overview" id="id55">Overview</a></li>
<li><a class="reference internal" href="#two-use-cases" id="id56">Two Use cases</a></li>
<li><a class="reference internal" href="#registering-an-objectfactory" id="id57">Registering an ObjectFactory</a></li>
<li><a class="reference internal" href="#asymmetry-between-retrieving-and-storing-objects" id="id58">Asymmetry between retrieving and storing objects</a></li>
<li><a class="reference internal" href="#storable-interface-and-object-serialization" id="id59">Storable Interface and Object serialization</a></li>
<li><a class="reference internal" href="#registering-singletons" id="id60">Registering Singletons</a></li>
<li><a class="reference internal" href="#historical-note" id="id61">Historical Note</a></li>
<li><a class="reference internal" href="#comparison-with-apache-derby" id="id62">Comparison with Apache Derby</a></li>
</ul>
</li>
<li><a class="reference internal" href="#storage-factory" id="id63">Storage Factory</a><ul>
<li><a class="reference internal" href="#id3" id="id64">Overview</a></li>
<li><a class="reference internal" href="#storage-containers" id="id65">Storage Containers</a></li>
<li><a class="reference internal" href="#storage-container-registry" id="id66">Storage Container Registry</a></li>
<li><a class="reference internal" href="#default-implementation" id="id67">Default Implementation</a></li>
</ul>
</li>
<li><a class="reference internal" href="#latch-manager" id="id68">Latch Manager</a><ul>
<li><a class="reference internal" href="#id4" id="id69">Overview</a></li>
<li><a class="reference internal" href="#latch-modes" id="id70">Latch modes</a></li>
<li><a class="reference internal" href="#implementation-and-performance-notes" id="id71">Implementation and Performance Notes</a></li>
<li><a class="reference internal" href="#obtaining-a-latch-instance" id="id72">Obtaining a latch instance</a></li>
</ul>
</li>
<li><a class="reference internal" href="#log-manager" id="id73">Log Manager</a><ul>
<li><a class="reference internal" href="#id5" id="id74">Overview</a></li>
<li><a class="reference internal" href="#write-ahead-log-wal-protocol" id="id75">Write Ahead Log (WAL) Protocol</a></li>
<li><a class="reference internal" href="#advantages-of-wal" id="id76">Advantages of WAL</a></li>
<li><a class="reference internal" href="#usage-notes" id="id77">Usage Notes</a></li>
<li><a class="reference internal" href="#simpledbm-implementation-of-the-log" id="id78">SimpleDBM Implementation of the Log</a></li>
<li><a class="reference internal" href="#limitations-of-current-design" id="id79">Limitations of current design</a></li>
<li><a class="reference internal" href="#operations" id="id80">Operations</a><ul>
<li><a class="reference internal" href="#creating-a-new-log-instance" id="id81">Creating a new Log Instance</a></li>
<li><a class="reference internal" href="#opening-a-log-instance" id="id82">Opening a log instance</a></li>
<li><a class="reference internal" href="#inserting-new-log-records" id="id83">Inserting new log records</a></li>
<li><a class="reference internal" href="#flushing-the-log" id="id84">Flushing the Log</a></li>
<li><a class="reference internal" href="#reading-log-records" id="id85">Reading Log records</a></li>
<li><a class="reference internal" href="#checkpoint-records" id="id86">Checkpoint Records</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#lock-manager" id="id87">Lock Manager</a><ul>
<li><a class="reference internal" href="#id6" id="id88">Introduction</a></li>
<li><a class="reference internal" href="#locking-basics" id="id89">Locking Basics</a></li>
<li><a class="reference internal" href="#two-phase-locking-and-repeatable-read-isolation-level" id="id90">Two-Phase Locking and Repeatable Read Isolation Level</a></li>
<li><a class="reference internal" href="#read-committed-isolation-level" id="id91">Read Committed Isolation Level</a></li>
<li><a class="reference internal" href="#serializable-isolation-level" id="id92">Serializable Isolation Level</a></li>
<li><a class="reference internal" href="#design-choices" id="id93">Design choices</a></li>
<li><a class="reference internal" href="#lock-modes" id="id94">Lock Modes</a><ul>
<li><a class="reference internal" href="#lock-compatibility-matrix" id="id95">Lock Compatibility Matrix</a></li>
<li><a class="reference internal" href="#lock-conversions" id="id96">Lock Conversions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#id7" id="id97">Operations</a><ul>
<li><a class="reference internal" href="#obtaining-an-instance-of-lock-manager" id="id98">Obtaining an instance of Lock Manager</a></li>
<li><a class="reference internal" href="#lockable-objects" id="id99">Lockable objects</a></li>
<li><a class="reference internal" href="#lock-owners" id="id100">Lock Owners</a></li>
<li><a class="reference internal" href="#lock-durations" id="id101">Lock Durations</a></li>
<li><a class="reference internal" href="#acquiring-and-releasing-locks" id="id102">Acquiring and releasing locks</a></li>
<li><a class="reference internal" href="#algorithm" id="id103">Algorithm</a><ul>
<li><a class="reference internal" href="#a001-lock-acquire" id="id104">a001 - lock acquire</a><ul>
<li><a class="reference internal" href="#main-success-scenario" id="id105">Main Success Scenario</a></li>
<li><a class="reference internal" href="#extensions" id="id106">Extensions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#a003-handle-new-request" id="id107">a003 - handle new request</a><ul>
<li><a class="reference internal" href="#id9" id="id108">Main Success Scenario</a></li>
<li><a class="reference internal" href="#id10" id="id109">Extensions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#a002-handle-lock-conversion" id="id110">a002 - handle lock conversion</a><ul>
<li><a class="reference internal" href="#id11" id="id111">Main Success Scenario</a></li>
<li><a class="reference internal" href="#id12" id="id112">Extensions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#a004-lock-wait" id="id113">a004 - lock wait</a><ul>
<li><a class="reference internal" href="#id13" id="id114">Main Success Scenario</a></li>
<li><a class="reference internal" href="#id14" id="id115">Extensions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#b001-release-lock" id="id116">b001 - release lock</a><ul>
<li><a class="reference internal" href="#id15" id="id117">Main Success Scenario</a></li>
<li><a class="reference internal" href="#id16" id="id118">Extensions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#b002-grant-waiters" id="id119">b002 - grant waiters</a><ul>
<li><a class="reference internal" href="#id17" id="id120">Main Success Scenario</a></li>
<li><a class="reference internal" href="#id18" id="id121">Extensions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#b003-grant-conversion-request" id="id122">b003 - grant conversion request</a><ul>
<li><a class="reference internal" href="#id19" id="id123">Main Success Scenario</a></li>
<li><a class="reference internal" href="#id20" id="id124">Extensions</a></li>
</ul>
</li>
<li><a class="reference internal" href="#c001-check-request-compatible-with-granted-group" id="id125">c001 - check request compatible with granted group</a><ul>
<li><a class="reference internal" href="#id21" id="id126">Main Success Scenario</a></li>
<li><a class="reference internal" href="#id22" id="id127">Extensions</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#data-structures-of-the-lock-manager" id="id128">Data Structures of the Lock Manager</a></li>
<li><a class="reference internal" href="#deadlock-detector" id="id129">Deadlock Detector</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#page-manager" id="id130">Page Manager</a><ul>
<li><a class="reference internal" href="#overview-of-page-manager-module" id="id131">Overview of Page Manager module</a></li>
<li><a class="reference internal" href="#interactions-with-other-modules" id="id132">Interactions with other modules</a></li>
<li><a class="reference internal" href="#page-class" id="id133">Page class</a><ul>
<li><a class="reference internal" href="#page-size-and-implementation-of-storable-interface" id="id134">Page Size and implementation of Storable interface</a></li>
<li><a class="reference internal" href="#how-various-page-types-are-managed" id="id135">How various Page types are managed</a></li>
<li><a class="reference internal" href="#page-factory" id="id136">Page Factory</a></li>
<li><a class="reference internal" href="#id25" id="id137">Page Manager</a></li>
<li><a class="reference internal" href="#storing-and-retrieving-pages" id="id138">Storing and retrieving Pages</a></li>
<li><a class="reference internal" href="#checksum" id="id139">Checksum</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#buffer-manager" id="id140">Buffer Manager</a><ul>
<li><a class="reference internal" href="#id26" id="id141">Overview</a></li>
<li><a class="reference internal" href="#id27" id="id142">Interactions with other modules</a></li>
<li><a class="reference internal" href="#id28" id="id143">Operations</a><ul>
<li><a class="reference internal" href="#creating-a-buffer-manager-instance" id="id144">Creating a Buffer Manager instance</a></li>
<li><a class="reference internal" href="#fixing-pages-in-the-buffer-pool" id="id145">Fixing Pages in the Buffer Pool</a></li>
<li><a class="reference internal" href="#modifying-page-contents" id="id146">Modifying page contents</a></li>
<li><a class="reference internal" href="#changing-lock-modes" id="id147">Changing lock modes</a></li>
<li><a class="reference internal" href="#unfixing-a-page" id="id148">Unfixing a Page</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#transaction-manager" id="id149">Transaction Manager</a><ul>
<li><a class="reference internal" href="#id29" id="id150">Introduction</a></li>
<li><a class="reference internal" href="#overiew" id="id151">Overiew</a></li>
<li><a class="reference internal" href="#what-is-aries" id="id152">What is ARIES?</a></li>
<li><a class="reference internal" href="#aries-an-overview" id="id153">ARIES - An Overview</a></li>
<li><a class="reference internal" href="#features-of-aries" id="id154">Features of ARIES</a></li>
<li><a class="reference internal" href="#key-differences-from-aries" id="id155">Key differences from ARIES</a></li>
<li><a class="reference internal" href="#transactions-and-locks" id="id156">Transactions and Locks</a></li>
<li><a class="reference internal" href="#transactions-and-modules" id="id157">Transactions and Modules</a></li>
<li><a class="reference internal" href="#transactions-and-log-records" id="id158">Transactions and Log records</a></li>
<li><a class="reference internal" href="#the-loggable-hierarchy" id="id159">The Loggable hierarchy</a><ul>
<li><a class="reference internal" href="#loggable-hierarchy" id="id160">Loggable Hierarchy</a></li>
<li><a class="reference internal" href="#transaction-manager-internal-log-records" id="id161">Transaction Manager Internal Log Records</a></li>
<li><a class="reference internal" href="#redoable" id="id162">Redoable</a></li>
<li><a class="reference internal" href="#baseloggable-abstract-class" id="id163">BaseLoggable abstract class</a></li>
<li><a class="reference internal" href="#pageformatoperation" id="id164">PageFormatOperation</a></li>
<li><a class="reference internal" href="#multipageredo" id="id165">MultiPageRedo</a></li>
<li><a class="reference internal" href="#undoable" id="id166">Undoable</a></li>
<li><a class="reference internal" href="#physical-undos" id="id167">Physical Undos</a></li>
<li><a class="reference internal" href="#singlepagelogicalundos" id="id168">SinglePageLogicalUndos</a></li>
<li><a class="reference internal" href="#logicalundos" id="id169">LogicalUndos</a></li>
<li><a class="reference internal" href="#comments-about-implementing-undo-operations" id="id170">Comments about implementing undo operations</a></li>
<li><a class="reference internal" href="#compensation-records" id="id171">Compensation records</a></li>
<li><a class="reference internal" href="#nontransactionrelatedoperations" id="id172">NonTransactionRelatedOperations</a></li>
<li><a class="reference internal" href="#postcommitactions" id="id173">PostCommitActions</a></li>
<li><a class="reference internal" href="#containerdeleteoperations" id="id174">ContainerDeleteOperations</a></li>
<li><a class="reference internal" href="#containeropenoperations" id="id175">ContainerOpenOperations</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#space-manager" id="id176">Space Manager</a><ul>
<li><a class="reference internal" href="#id33" id="id177">Introduction</a></li>
<li><a class="reference internal" href="#comparison-with-storage-manager-module" id="id178">Comparison with Storage Manager module</a></li>
<li><a class="reference internal" href="#id34" id="id179">Operations</a><ul>
<li><a class="reference internal" href="#obtaining-an-instance-of-spacemgr" id="id180">Obtaining an instance of SpaceMgr</a></li>
<li><a class="reference internal" href="#creating-a-container" id="id181">Creating a Container</a></li>
<li><a class="reference internal" href="#extending-a-container" id="id182">Extending a Container</a></li>
<li><a class="reference internal" href="#deleting-a-container" id="id183">Deleting a container</a></li>
<li><a class="reference internal" href="#searching-for-free-space" id="id184">Searching for free space</a></li>
<li><a class="reference internal" href="#updating-space-information" id="id185">Updating space information</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#slotted-page-manager" id="id186">Slotted Page Manager</a><ul>
<li><a class="reference internal" href="#id35" id="id187">Introduction</a></li>
<li><a class="reference internal" href="#structure-of-slotted-page" id="id188">Structure of Slotted Page</a></li>
<li><a class="reference internal" href="#obtaining-instances-of-slotted-page" id="id189">Obtaining instances of Slotted Page</a></li>
<li><a class="reference internal" href="#inserting-or-updating-records" id="id190">Inserting or updating records</a></li>
<li><a class="reference internal" href="#deleting-records" id="id191">Deleting records</a></li>
<li><a class="reference internal" href="#accessing-records" id="id192">Accessing records</a></li>
<li><a class="reference internal" href="#miscellaneous-operations" id="id193">Miscellaneous operations</a></li>
</ul>
</li>
<li><a class="reference internal" href="#index-manager" id="id194">Index Manager</a><ul>
<li><a class="reference internal" href="#id36" id="id195">Overview</a></li>
<li><a class="reference internal" href="#challenges-with-b-tree-concurrency" id="id196">Challenges with B-Tree Concurrency</a><ul>
<li><a class="reference internal" href="#survey-of-algorithms" id="id197">Survey of algorithms</a></li>
<li><a class="reference internal" href="#limitations-of-lehman-and-yao-b-link-trees" id="id198">Limitations of Lehman and Yao B-link Trees</a></li>
<li><a class="reference internal" href="#recoverable-b-link-trees" id="id199">Recoverable B-Link Trees</a></li>
<li><a class="reference internal" href="#b-tree-algorithm-in-apache-derby" id="id200">B-Tree algorithm in Apache Derby</a></li>
<li><a class="reference internal" href="#simpledbm-b-link-tree" id="id201">SimpleDBM B-link Tree</a></li>
</ul>
</li>
<li><a class="reference internal" href="#structure-of-the-b-link-tree" id="id202">Structure of the B-link Tree</a></li>
<li><a class="reference internal" href="#structure-of-nodes" id="id203">Structure of Nodes</a><ul>
<li><a class="reference internal" href="#id42" id="id204">Overview</a></li>
<li><a class="reference internal" href="#leaf-nodes" id="id205">Leaf Nodes</a></li>
<li><a class="reference internal" href="#index-nodes" id="id206">Index Nodes</a></li>
<li><a class="reference internal" href="#limits" id="id207">Limits</a></li>
</ul>
</li>
<li><a class="reference internal" href="#key-differences-from-published-algorithm" id="id208">Key Differences from published algorithm</a><ul>
<li><a class="reference internal" href="#support-for-non-unique-indexes" id="id209">Support for Non-Unique indexes</a></li>
<li><a class="reference internal" href="#handling-of-storage-map" id="id210">Handling of storage map</a></li>
<li><a class="reference internal" href="#variable-length-keys" id="id211">Variable length keys</a></li>
<li><a class="reference internal" href="#page-split-operation" id="id212">Page Split operation</a></li>
<li><a class="reference internal" href="#merge-operation" id="id213">Merge Operation</a></li>
<li><a class="reference internal" href="#link-operation" id="id214">Link Operation</a></li>
<li><a class="reference internal" href="#unlink-operation" id="id215">Unlink Operation</a></li>
<li><a class="reference internal" href="#redistribute-keys-operation" id="id216">Redistribute Keys Operation</a></li>
<li><a class="reference internal" href="#increase-tree-height-operation" id="id217">Increase Tree Height Operation</a></li>
<li><a class="reference internal" href="#decrease-tree-height-operation" id="id218">Decrease Tree Height Operation</a></li>
<li><a class="reference internal" href="#index-scans" id="id219">Index Scans</a></li>
<li><a class="reference internal" href="#simplified-algorithm-for-scans" id="id220">Simplified Algorithm for Scans</a></li>
<li><a class="reference internal" href="#simpler-page-modification-checks" id="id221">Simpler page modification checks</a></li>
<li><a class="reference internal" href="#b-tree-index-is-a-secondary-structure" id="id222">B-Tree index is a secondary structure</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference internal" href="#tuple-manager" id="id223">Tuple Manager</a><ul>
<li><a class="reference internal" href="#overview-of-tuple-manager" id="id224">Overview of Tuple Manager</a></li>
<li><a class="reference internal" href="#design-decisions" id="id225">Design Decisions</a><ul>
<li><a class="reference internal" href="#tuple-inserts" id="id226">Tuple Inserts</a></li>
<li><a class="reference internal" href="#tuple-segmentation" id="id227">Tuple Segmentation</a></li>
<li><a class="reference internal" href="#tuple-deletes" id="id228">Tuple Deletes</a></li>
<li><a class="reference internal" href="#tuple-updates" id="id229">Tuple Updates</a></li>
<li><a class="reference internal" href="#space-reclamation" id="id230">Space Reclamation</a></li>
<li><a class="reference internal" href="#tuple-segment-structure" id="id231">Tuple Segment Structure</a></li>
<li><a class="reference internal" href="#free-space-information" id="id232">Free Space Information</a></li>
<li><a class="reference internal" href="#latch-ordering" id="id233">Latch Ordering</a></li>
<li><a class="reference internal" href="#logging-of-space-map-page-updates" id="id234">Logging of Space Map Page updates</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
<div class="section" id="introduction">
<h2><a class="toc-backref" href="#id50">Introduction</a><a class="headerlink" href="#introduction" title="Permalink to this headline">¶</a></h2>
<p>This document describes the SimpleDBM Internals.</p>
<div class="section" id="intended-audience">
<h3><a class="toc-backref" href="#id51">Intended Audience</a><a class="headerlink" href="#intended-audience" title="Permalink to this headline">¶</a></h3>
<p>This documented is targetted at <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> developers.</p>
</div>
<div class="section" id="pre-requisite-reading">
<h3><a class="toc-backref" href="#id52">Pre-requisite Reading</a><a class="headerlink" href="#pre-requisite-reading" title="Permalink to this headline">¶</a></h3>
<p>Before reading this document, the reader is advised to go through
the <a class="reference external" href="http://simpledbm.googlecode.com/hg/simpledbm-docs/docs/html/overview.html">SimpleDBM Overview</a> document.</p>
</div>
</div>
<div class="section" id="data-manager-rss-components">
<h2><a class="toc-backref" href="#id53">Data Manager/RSS Components</a><a class="headerlink" href="#data-manager-rss-components" title="Permalink to this headline">¶</a></h2>
<p>The Data Manager/Relational Storage system (RSS) consists of the
components listed in the table given below.</p>
<table border="1" class="docutils">
<colgroup>
<col width="21%" />
<col width="79%" />
</colgroup>
<thead valign="bottom">
<tr><th class="head">Module Name</th>
<th class="head">Description</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>Logging</td>
<td>Provides a Logger interface that hides the
implementation details. Can wrap either JDK
logging or Log4J.</td>
</tr>
<tr><td>Utility</td>
<td>Contains miscellaneous utility classes.</td>
</tr>
<tr><td>Registry</td>
<td>Provides the Object Registry, which is a
factory for creating objects based on type
code.</td>
</tr>
<tr><td>Storage
Manager</td>
<td>Provides an abstraction for input/output of
storage containers similar to files.</td>
</tr>
<tr><td>Latch</td>
<td>Provides read/write locks that can be used
to manage concurrency.</td>
</tr>
<tr><td>Lock Manager</td>
<td>Implements a Lock Scheduler that allows
locking of arbitrary objects. Several
different lock modes are supported.</td>
</tr>
<tr><td>Page Manager</td>
<td>The Page Manager defines the page size and
provides mapping of pages to storage
containers.</td>
</tr>
<tr><td>Buffer
Manager</td>
<td>The Buffer Manager module implements the
Page Cache where recently accessed pages are
stored temporarily.</td>
</tr>
<tr><td>Log Manager</td>
<td>The Write Ahead Log Manager is used for
recording changes made to the database for
recovery purposes.</td>
</tr>
<tr><td>Transaction
Manager</td>
<td>The Transaction Manager manages
transactions, system restart and recovery.</td>
</tr>
<tr><td>Free Space
Manager</td>
<td>The Free Space Manager is responsible for
managing free space information in storage
containers.</td>
</tr>
<tr><td>Slotted Page
Manager</td>
<td>The Slotted Page Manager provides an common
implementation of pages containing multiple
records. A slot table is used to provide a
level of indirection to the records. This
allows records to be moved within the page
without affecting clients.</td>
</tr>
<tr><td>Location</td>
<td>The Location module specifies the interface
for identifying lockable records in storage
containers.</td>
</tr>
<tr><td>Index
Manager</td>
<td>Provides efficient structures for accessing
locations based upon key values.</td>
</tr>
<tr><td>Tuple
Manager</td>
<td>Provides an implementation of tuple
containers. A tuple is defined as variable
sized blob of data that has a unique
identity within the tuple container.</td>
</tr>
<tr><td>Server</td>
<td>This brings together all the other modules
and provides overall management of the
SimpleDBM RSS database engine.</td>
</tr>
</tbody>
</table>
</div>
<div class="section" id="object-registry">
<h2><a class="toc-backref" href="#id54">Object Registry</a><a class="headerlink" href="#object-registry" title="Permalink to this headline">¶</a></h2>
<div class="section" id="overview">
<h3><a class="toc-backref" href="#id55">Overview</a><a class="headerlink" href="#overview" title="Permalink to this headline">¶</a></h3>
<p>SimpleDBM uses a custom serialization mechanism for marshalling
and unmarshalling objects to/from byte streams. When an object
is marshalled, a two-byte code is stored in the first two bytes of
the byte stream <a class="footnote-reference" href="#id2" id="id1">[1]</a>. This identifies the class of the stored object.
When reading back, the type code is used to lookup a factory for
creating the object of the correct class.</p>
<table class="docutils footnote" frame="void" id="id2" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id1">[1]</a></td><td>In some cases the type code is not stored, as it can be
determined through some other means.</td></tr>
</tbody>
</table>
<p>The SimpleDBM serialization mechanism does not use the Java
Serialization framework.</p>
<p>Central to the SimpleDBM serialization mechanism is the <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt>
module. The <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt> provides the coupling between SimpleDBM
serialization mechanism and its clients. For instance, index key
types, table row types, etc. are registered in SimpleDBM&#8217;s
<tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt> and thereby made available to SimpleDBM. You will
see how this is done when we discuss Tables and
Indexes.</p>
<p>To allow SimpleDBM to serialize and deserialize an object from a byte-stream,
you must:</p>
<ol class="arabic simple">
<li>Assign a unique 2-byte (short) type code to the class. Because the type
code gets recorded in persistent storage,
it must be stable, i.e., once registered, the type code association
for a class must remain constant for the life span of the
the database.</li>
<li>Ensure that the class implements a constructor that takes a
ByteBuffer argument. The constructor should expect the first two bytes
to contain the typecode for the class.</li>
<li>Ensure that the class implements the Storable interface. The
stored length of an object of the class must allow for the 2-byte
type code.</li>
<li>Provide an implementation of the <tt class="docutils literal"><span class="pre">org.simpledbm.rss.api.registry.ObjectFactory</span></tt>
interface, and register this implementation with the <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt>.</li>
</ol>
<p>An important consideration is to ensure that all the required classes
are available to a SimpleDBM RSS instance at startup.</p>
<p>A limitation of the current design is that the type registrations are
not held in persistent storage. Since all type mappings must be available
to SimpleDBM server when it is starting up (as these may be involved
in recovery) you need to ensure that custom type mappings are registered
to the <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt> immediately after the server instance is constructed, but
before the server is started. Typically this is handled by requiring
each module to register its own types.</p>
<p>Type codes between the range 0-1000 are reserved for use by
SimpleDBM.</p>
</div>
<div class="section" id="two-use-cases">
<h3><a class="toc-backref" href="#id56">Two Use cases</a><a class="headerlink" href="#two-use-cases" title="Permalink to this headline">¶</a></h3>
<p>The <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt> supports two use cases.</p>
<ul class="simple">
<li>The first use case is where the client registers an <tt class="docutils literal"><span class="pre">ObjectFactory</span></tt>
implementation. In this case, <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt> can construct the
correct object from a byte stream on request. By taking care of the
common case, the client code is simplified.</li>
<li>The second case is when the client has a more complex requirement
and wants to manage the instantiation of objects. In this scenario,
the client registers a singleton class and associates this with the
type code. The <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt> will return the registered singleton
object when requested.</li>
</ul>
</div>
<div class="section" id="registering-an-objectfactory">
<h3><a class="toc-backref" href="#id57">Registering an ObjectFactory</a><a class="headerlink" href="#registering-an-objectfactory" title="Permalink to this headline">¶</a></h3>
<p>In the simple case, an <tt class="docutils literal"><span class="pre">ObjectFactory</span></tt> implementation needs to be
registered for a particular type code.</p>
<p>In the example shown below, objects of the class <tt class="docutils literal"><span class="pre">MyObject</span></tt>
are to be persisted:</p>
<div class="highlight-python"><pre>public final class MyObject implements Storable {
  final int value;

  /**
   * Constructs a MyObject from a byte stream.
   */
  public MyObject(ByteBuffer buf) {
    // skip the type code
    buf.getShort();
    // now get the value
    value = buf.getInt();
  }

  /* Storable methods not shown */
}</pre>
</div>
<p>Points worth noting are:</p>
<ul class="simple">
<li>The <tt class="docutils literal"><span class="pre">MyObject</span></tt> class provides a constructor that takes a <tt class="docutils literal"><span class="pre">ByteBuffer</span></tt>
as an argument. This is important as it allows the object to
use final fields, allowing the class to be immutable.</li>
<li>The constructor skips the first two bytes which contain the type code.</li>
</ul>
<p>We need an <tt class="docutils literal"><span class="pre">ObjectFactory</span></tt> implementation that constructs the <tt class="docutils literal"><span class="pre">MyObject</span></tt>
instances. The implementation is relatively straightforward:</p>
<div class="highlight-python"><pre>class MyObjectFactory implements ObjectFactory {
  Object getInstance(ByteBuffer buf) {
    return new MyObject(buf);
  }
}</pre>
</div>
<p>Next, we register the <tt class="docutils literal"><span class="pre">ObjectFactory</span></tt> implementation with the <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt>.:</p>
<div class="highlight-python"><pre>objectRegistry.registerObjectFactory(1, new MyObjectFactory());</pre>
</div>
<p>Given above registration, it is possible to
construct MyObject instances as follows:</p>
<div class="highlight-python"><pre>ByteBuffer buf = ...;
MyObject o = (MyObject) objectRegistry.getInstance(buf);</pre>
</div>
<p>This pattern is used throughout SimpleDBM RSS.</p>
</div>
<div class="section" id="asymmetry-between-retrieving-and-storing-objects">
<h3><a class="toc-backref" href="#id58">Asymmetry between retrieving and storing objects</a><a class="headerlink" href="#asymmetry-between-retrieving-and-storing-objects" title="Permalink to this headline">¶</a></h3>
<p>The reader may have noticed that the <tt class="docutils literal"><span class="pre">ObjectFactory</span></tt> says
nothing about how objects are marshalled into a byte stream.
It only deals with the unmarshalling of objects.</p>
<p>The marshalling is handled by the object itself. All
objects that support marshalling are required to implement
the Storable interface.</p>
</div>
<div class="section" id="storable-interface-and-object-serialization">
<h3><a class="toc-backref" href="#id59">Storable Interface and Object serialization</a><a class="headerlink" href="#storable-interface-and-object-serialization" title="Permalink to this headline">¶</a></h3>
<p>Classes that need serialization support should implement
the interface <tt class="docutils literal"><span class="pre">org.simpledbm.rss.api.registry.Storable</span></tt>.
The <tt class="docutils literal"><span class="pre">Storable</span></tt> interface requires the object
to be able to predict its persistent size in bytes when the
<tt class="docutils literal"><span class="pre">getStoredLength()</span></tt> method is invoked. It also requires the
implementation to be able to stream itself to a <tt class="docutils literal"><span class="pre">ByteBuffer</span></tt>.</p>
<p>The Storable interface specification is as follows:</p>
<div class="highlight-python"><pre>/**
 * A Storable object can be written to (stored into) or
 * read from (retrieved from) a ByteBuffer. The object
 * must be able to predict its length in bytes;
 * this not only allows clients to allocate ByteBuffer
 * objects of suitable size, it is also be used by a
 * StorageContainer to ensure that objects can be
 * restored from secondary storage.
 */
public interface Storable {

  /**
   * Store this object into the supplied ByteBuffer in
   * a format that can be subsequently used to reconstruct the
   * object. ByteBuffer is assumed to be setup
   * correctly for writing.
   *
   * @param bb ByteBuffer that will contain a stored
   *           representation of the object.
   */
  void store(ByteBuffer bb);

  /**
   * Predict the length of this object in bytes when
   * stored in a ByteBuffer.
   *
   * @return The length of this object when stored in
   *         a ByteBuffer.
   */
  int getStoredLength();
}</pre>
</div>
<p>The implementation of the <tt class="docutils literal"><span class="pre">store()</span></tt> method must be the inverse
of the constructor that takes the <tt class="docutils literal"><span class="pre">ByteBuffer</span></tt> argument.</p>
<p>A complete example of the <tt class="docutils literal"><span class="pre">MyObject</span></tt> class will look like
this:</p>
<div class="highlight-python"><pre>public final class MyObject implements Storable {
  final int value;

  /**
   * Constructs a MyObject from a byte stream.
   */
  public MyObject(ByteBuffer buf) {
    // skip the type code
    buf.getShort();
    // now get the value
    value = buf.getInt();
  }

  public int getStoredLength() {
    return 6;
  }

  /**
   * Serialize to a ByteBuffer object.
   */
  public void store(ByteBuffer bb) {
    bb.putShort((short) 1);
    bb.putInt(value);
  }
}</pre>
</div>
</div>
<div class="section" id="registering-singletons">
<h3><a class="toc-backref" href="#id60">Registering Singletons</a><a class="headerlink" href="#registering-singletons" title="Permalink to this headline">¶</a></h3>
<p>In some cases, the requirements for constructing objects are complex
enough for the client to manage it itself. In this case, the client
provides a singleton object that is registered with the <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt>.
The <tt class="docutils literal"><span class="pre">ObjectRegistry.getSingleton(int</span> <span class="pre">typecode)</span></tt> method retrieves the
Singleton object. Typically, the singleton is a factory class that can
be used to create new instances of objects.</p>
</div>
<div class="section" id="historical-note">
<h3><a class="toc-backref" href="#id61">Historical Note</a><a class="headerlink" href="#historical-note" title="Permalink to this headline">¶</a></h3>
<p>The initial design of SimpleDBM&#8217;s <tt class="docutils literal"><span class="pre">ObjectRegistry</span></tt> used reflection
to create instances of objects. Instead of registering factory classes,
the name of the target class was registered.</p>
<p>The unmarshalling of objects was performed in two steps. First, the
no-arg constructor was invoked to construct the object. Then a
method on the Storable interface was invoked to deserialize the
object&#8217;s fields from the ByteBuffer.</p>
<p>This method was abandoned in favour of the current approach due to
following problems.</p>
<ul class="simple">
<li>Firstly, it required that all classes that participated in the
persistence mechanism support a no-arg constructor.</li>
<li>Fields could not be final, as the fields needed to be initialized post
construction. As a result, persistent classes could not be immutable.</li>
<li>It was difficult to supply additional arguments (context information)
to the constructed objects. This was because the object was constructed
by a third-party, which had no knowledge about the object.</li>
<li>It used reflection to construct objects.</li>
</ul>
<p>The current method overcomes these problems, and has resulted in
more robust code.</p>
</div>
<div class="section" id="comparison-with-apache-derby">
<h3><a class="toc-backref" href="#id62">Comparison with Apache Derby</a><a class="headerlink" href="#comparison-with-apache-derby" title="Permalink to this headline">¶</a></h3>
<p>Apache Derby has a similar requirement to marshall and unmarshall objects
to/from a byte stream. The solution used by Derby
is different from SimpleDBM in following ways.</p>
<ul class="simple">
<li>It uses a custom implementation of the Java Serialization mechanism.</li>
<li>Reflection is used to obtain instances of objects.</li>
<li>The type code database is hard-coded in a static class. In SimpleDBM,
types are added by each module; there is no central hard-coded list of
types.</li>
</ul>
</div>
</div>
<div class="section" id="storage-factory">
<h2><a class="toc-backref" href="#id63">Storage Factory</a><a class="headerlink" href="#storage-factory" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id3">
<h3><a class="toc-backref" href="#id64">Overview</a><a class="headerlink" href="#id3" title="Permalink to this headline">¶</a></h3>
<p>Database Managers typically use files to store various types of
data, such as log files, data files, etc.. However, from the
perspective of a DBMS, the concept of a file is a logical one; all
the DBMS cares about is a named storage container that supports
random positioned IO. As long as this requirement is met, it is not
important whether a container maps to a file or to some other
device.</p>
<p>The objective of the StorageFactory package is to provide a level of abstraction
to the rest of the DBMS so that the mapping of a container to a file
becomes an implementation artefact. If desired, containers may be
mapped to raw devices, or to segments within a file.</p>
</div>
<div class="section" id="storage-containers">
<h3><a class="toc-backref" href="#id65">Storage Containers</a><a class="headerlink" href="#storage-containers" title="Permalink to this headline">¶</a></h3>
<p>A Storage Container is a named entity that supports positioned
(random) Input/Output. The default implementation maps a container
to a file, but this is an implementation detail, and not a requirement.
The rest of the system does not need to know what the storage
container maps to.</p>
<p>The operations on storage containers are similar to those that can
be performed on files.</p>
<p>In <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>, each table or index maps to a single storage
container. The Write Ahead Log also uses storage containers to store
its data. Table and index containers have fixed size pages. The
Write Ahead Log contains variable size records.</p>
</div>
<div class="section" id="storage-container-registry">
<h3><a class="toc-backref" href="#id66">Storage Container Registry</a><a class="headerlink" href="#storage-container-registry" title="Permalink to this headline">¶</a></h3>
<p>Container names are usually not good identifiers for the rest of the
system. Integer identifiers are better, especially when other
objects need to refer to specific containers. Integers take less
amount of storage, and also remove the dependency between the
container&#8217;s name and the rest of the system. To support this
requirement, the <tt class="docutils literal"><span class="pre">org.simpledbm.rss.api.st.StorageManager</span></tt>
interface is provided, which maintains a mapping of
StorageContainers to integer identifiers. Note that the Storage
sub-system does not decide how to map the containers to ids; it
merely enables the registration of these mappings and allows
StorageContainer objects to be retrieved using their numeric
identifiers.</p>
<div class="highlight-python"><pre>StorageContainerFactory storageFactory
   = new FileStorageContainerFactory();
StorageManager storageManager = new StorageManagerImpl();
StorageContainer sc = storageFactory.open("dual");
storageManager.register(0, sc);</pre>
</div>
<p>Above sample code registers the container named &#8220;dual&#8221; to the
storage manager and identifies this with the integer value 0. Other
modules may obtain access to the storage container as follows:</p>
<div class="highlight-python"><pre>StorageContainer sc = storageManager.getInstance(0);</pre>
</div>
</div>
<div class="section" id="default-implementation">
<h3><a class="toc-backref" href="#id67">Default Implementation</a><a class="headerlink" href="#default-implementation" title="Permalink to this headline">¶</a></h3>
<p>The default implementation of the StorageFactory uses a
<tt class="docutils literal"><span class="pre">RandomAccessFile</span></tt> as the underlying container. A few
configuration options are supported to allow changing the
behaviour of certain performance sensitive operations. These
are listed below.</p>
<table border="1" class="docutils">
<colgroup>
<col width="30%" />
<col width="70%" />
</colgroup>
<thead valign="bottom">
<tr><th class="head">Option</th>
<th class="head">Description</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>storage.basePath</td>
<td>This is used to specify the base directory
relative to which all storage container
instances are to be created.</td>
</tr>
<tr><td>storage.createMode</td>
<td>This is used to set the <tt class="docutils literal"><span class="pre">RandomAccessFile</span></tt>
mode that is used when creating a container.</td>
</tr>
<tr><td>storage.openMode</td>
<td>This is used to set the <tt class="docutils literal"><span class="pre">RandomAccessFile</span></tt>
mode when a container is opened.</td>
</tr>
<tr><td>storage.flushMode</td>
<td>The flushMode has two values:
force.true causes force(true) to be invoked
on the file channel when the container is
flushed.
force.false causes force(false) to be
ivoked. A missing flushMode causes the call
to force() to do nothing.</td>
</tr>
</tbody>
</table>
<p>Note that some of the modes can have a big impact on performance of
SimpleDBM.</p>
</div>
</div>
<div class="section" id="latch-manager">
<h2><a class="toc-backref" href="#id68">Latch Manager</a><a class="headerlink" href="#latch-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id4">
<h3><a class="toc-backref" href="#id69">Overview</a><a class="headerlink" href="#id4" title="Permalink to this headline">¶</a></h3>
<p>A Latch is an efficient lock that is used by the system to manage
concurrent access to physical structures. In many ways, Latches are
similar to Mutexes, however, latches supports additional lock modes,
such as Shared locks and Update locks.</p>
</div>
<div class="section" id="latch-modes">
<h3><a class="toc-backref" href="#id70">Latch modes</a><a class="headerlink" href="#latch-modes" title="Permalink to this headline">¶</a></h3>
<p><a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> implements two types of latches. A ReadWrite Latch
supports two lock modes:</p>
<dl class="docutils">
<dt>Shared mode</dt>
<dd>is compatible with Shared mode but incompatible with Exclusive</dd>
<dt>Exclusive mode</dt>
<dd>incompatible with any other mode.</dd>
</dl>
<p>A ReadWriteUpdate latch is an enhanced version that supports an
additional Update mode lock.</p>
<dl class="docutils">
<dt>Update mode</dt>
<dd>compatible with Shared mode but incompatible with
Update or Exclusive modes. Note that the Shared mode locks are
incompatible with Update mode locks.</dd>
</dl>
<p>An Update lock may be upgraded to Exclusive lock, and conversely, an
Exclusive lock may be downgraded to an Update lock. An Update lock
may also be downgraded to a Shared lock.</p>
</div>
<div class="section" id="implementation-and-performance-notes">
<h3><a class="toc-backref" href="#id71">Implementation and Performance Notes</a><a class="headerlink" href="#implementation-and-performance-notes" title="Permalink to this headline">¶</a></h3>
<p>The <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> Latch interface is designed to be compatible with the
Java 5.0 <tt class="docutils literal"><span class="pre">ReentrantReadWriteLock</span></tt> interface. This allows the <tt class="docutils literal"><span class="pre">ReadWrite</span></tt>
Latch implementation to be based upon the Java primitive.</p>
<p>The <tt class="docutils literal"><span class="pre">ReadWrite</span></tt> Latch is likely to be more efficient than the
<tt class="docutils literal"><span class="pre">ReadWriteUpdate</span></tt> Latch.</p>
<p>The <tt class="docutils literal"><span class="pre">ReadWriteUpdate</span></tt> latch implementation uses a subset of the <tt class="docutils literal"><span class="pre">LockManager</span></tt> implementation
described later in this document. There are a few differences between the two
implementations:</p>
<ul class="simple">
<li>Unlike a Lock, which has to be looked up dynamically in a hash table, a latch is known to its client,
and hence no lookup is necessary. Each instance of a latch is a lock. Clients hold a reference
to the latch.</li>
<li>There is no support for various lock durations as these do not make
sense here.</li>
<li>Apart from lock conversions and downgrades, we also support lock upgrades.
An upgrade is like a conversion except that it is explicitly requested and does
not cause the reference count to go up. Hence the difference is primarily in the way
clients use locks. For normal lock conversions, clients are expected to treat
each request as a separate request, and therefore release the lock as many
times as requested. Upgrade (and downgrade) requests do not modify the reference
count.</li>
<li>Unlike Lock Manager, the owner for latches is predefined - it is always the
requesting thread. Hence there is no need to supply an owner.</li>
<li>Latches do not support deadlock detection. The implementation uses a timeout of
10 seconds which is a simple way of detecting latch deadlocks. Note that Latch
deadlocks are always due to bugs in the code, and should never occur at runtime.
Such deadlocks are avoided by ensuring that latches are acquired and released in a specific order.</li>
</ul>
</div>
<div class="section" id="obtaining-a-latch-instance">
<h3><a class="toc-backref" href="#id72">Obtaining a latch instance</a><a class="headerlink" href="#obtaining-a-latch-instance" title="Permalink to this headline">¶</a></h3>
<p><a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> implements a factory class for creating Latch objects. The
factory supports instantiating a ReadWrite latch, or a
ReadWriteUpdate latch. There is also a default mode which results in
ReadWrite latch.</p>
</div>
</div>
<div class="section" id="log-manager">
<h2><a class="toc-backref" href="#id73">Log Manager</a><a class="headerlink" href="#log-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id5">
<h3><a class="toc-backref" href="#id74">Overview</a><a class="headerlink" href="#id5" title="Permalink to this headline">¶</a></h3>
<p>The Write Ahead Log plays a crucial role in a DBMS. It provides the
basis for recoverability. It is also a critical part of the system
that has a massive impact on performance of an OLTP system.</p>
<p>Conceptually, the Log can be thought of as an ever growing
sequential file. In the form of Log Records, the Log contains a
history of all changes made to the database. Each Log Record is
uniquely identified by a number called the Log Sequence Number
(LSN). The LSN is designed in such a way that given an LSN, the
system can locate the corresponding Log Record quickly. LSNs are
assigned in strict ascending order (monotonicity). This is an
important property when it comes to recovery.</p>
<p>During the progress of a Transaction, the a DBMS records in the Log
all the changes made by the transaction. The Log records can be used
to recover the system if there is a failure, or they can be used to
undo the changes made by a transaction.</p>
<p>Initially, Log Records are stored in memory. They are flushed to
disk during transaction commits, and also during checkpoints. In the
event of a crash, it is possible to lose the log records that were
not flushed to disk. This does not cause a problem, however, because
by definition these log records must correspond to changes made by
incomplete transactions. Also, the WAL protocol (described below)
ensures that such Log records do not contain changes that have
already been persisted within the database.</p>
</div>
<div class="section" id="write-ahead-log-wal-protocol">
<h3><a class="toc-backref" href="#id75">Write Ahead Log (WAL) Protocol</a><a class="headerlink" href="#write-ahead-log-wal-protocol" title="Permalink to this headline">¶</a></h3>
<p>The WAL protocol requires the following conditions to hold true:</p>
<ol class="arabic simple">
<li>All changes made by a transaction must be recorded in the Log
and the Log must be flushed to disk before the transaction is
committed.</li>
<li>A database buffer page may not be modified until its modifications
have been logged. A buffer page may not be saved to disk until
all its associated log records have been saved to disk.</li>
<li>While the buffer page is being modified and the Log is being
updated, an Exclusive latch (a type of fast lock) must be held
on the page to ensure that order in which changes are recorded
in the Log correspond to the order in which they were made.</li>
</ol>
<p>Consequences of above rules are:</p>
<ul class="simple">
<li>If a Log Record was not saved to disk, it can be safely ignored,
because any changes contained in it are guaranteed to belong to
uncommitted transactions. Also, such Log Records cannot represent
changes that have been made persistent in the database.</li>
<li>Log records represent changes to the system in the correct order.
The latching protocol ensures that if two Log records represent
changes to the same Page, then the ordering of these records
reflects the order in which the changes were made to the page.</li>
</ul>
</div>
<div class="section" id="advantages-of-wal">
<h3><a class="toc-backref" href="#id76">Advantages of WAL</a><a class="headerlink" href="#advantages-of-wal" title="Permalink to this headline">¶</a></h3>
<p>Typically, in an OLTP system, updates tend to be random and can
affect different parts of the disk at a point in time. In
comparison, writes to the Log are always sequential. If it were
necessary to flush all changes made by the DBMS to disk at commit
time, it would have a massive impact on performance because of the
randomness of the disk writes. However, in a WAL system, only the
Log needs to be flushed to disk at Commit. Thus, the Log has the
effect of transforming random writes into serial writes, thereby
improving performance significantly.</p>
</div>
<div class="section" id="usage-notes">
<h3><a class="toc-backref" href="#id77">Usage Notes</a><a class="headerlink" href="#usage-notes" title="Permalink to this headline">¶</a></h3>
<p>The Log Manager interface does not make any assumptions about log
records. In fact, it does not specify the format of a log record.</p>
</div>
<div class="section" id="simpledbm-implementation-of-the-log">
<h3><a class="toc-backref" href="#id78">SimpleDBM Implementation of the Log</a><a class="headerlink" href="#simpledbm-implementation-of-the-log" title="Permalink to this headline">¶</a></h3>
<p>The <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> Log maintains control information separately from log
files. For safety, multiple copies of control information are stored
(though at present, only the first control file is used when opening
the Log).</p>
<p>Logically, the Log is organized as a never ending sequence of log
records. Physically, the Log is split up into log files. There is a
fixed set of online log files, and a dynamic set of archived log
files. The set of online log files is called a Log Group.</p>
<p>Each Log Group consists of a set of pre-allocated log files of the
same size. The maximum number of groups possible is 3, and the
maximum number of log files within a group is 8. Note that each
group is a complete set in itself - the Log is recoverable if any
one of the groups is available, and if the archived log files are
available. If more than one group is created, it is expected that
each group will reside on a different disk sub-system.</p>
<p>The Log Groups are allocated when the Log is initially created. The
log files within a group are also pre-allocated. However, the
content of the online log files changes over time.</p>
<p>Logically, in the same way that the Log can be viewed as a sequence
of Log Records, it can also be thought of as a sequence of Log
Files. The Log Files are numbered in sequence, starting from 1. The
Log File sequence number is called LogIndex. At any point in time,
the physical set of online log files will contain a set of logical
log files. For example, if there are 3 physical files in a Log
Group, then at startup, the set of logical log files would be 1, 2
and 3. After some time, the log file 1 would get archived, and in
its place a new logical log file 4 would be created. The set now
would now consist of logical log files 2, 3 and 4.</p>
<p>When a log record is written to disk, it is written out to an online
log file. If there is more than one group, then the log record is
written to each of the groups. The writes happen in sequence to
ensure that if there is a write failure, damage is restricted to one
Log Group. Note that due to the way this works, having more than 1
group will slow down log writes. It is preferable to use hardware
based disk mirroring of log files as opposed to using multiple log
groups.</p>
<p>When new log records are created, they are initially stored in the
log buffers. Log records are written out to log files either because
of a client request to flush the log, or because of the periodic
flush event.</p>
<p>During a flush, the system determines which log file to use. There
is the notion of Current log file, which is where writes are
expected to occur. If the current log file is full, it is put into a
queue for archiving, and the log file is switched. Until an online
log file has been archived, its physical file cannot be reused. A
separate archive thread monitors archive requests and archives log
files in the background.</p>
<p>Only one flush is permitted to execute at any point in time.
Similarly, only one archive is permitted to execute at any point in
time. However, multiple clients are allowed to concurrently insert
and read log records, even while flushing and archiving is going on,
except under following circumstances.</p>
<ol class="arabic simple">
<li>Log inserts cannot proceed if the system has used up more
memory than it should. In that case, it must wait for some memory to
be freed up. To ensure maximum concurrency, the memory calculation
is approximate.</li>
<li>A Log flush cannot proceed if all the online log files are full.
In this situation, the flush must wait for at least one file to be
archived.</li>
<li>When reading a log record, if the online log file containing the
record is being archived, the reader may have to wait for the status
of the log file to change, before proceeding with the read.
Conversely, if a read is active, the archive thread must wait for
the read to be over before changing the status of the log file.</li>
</ol>
<p>If archive mode is ON, log files are archived before being re-used.
Otherwise, they can be reused if the file is no longer needed -
however this is currently not implemented. By default archive mode
is ON.</p>
</div>
<div class="section" id="limitations-of-current-design">
<h3><a class="toc-backref" href="#id79">Limitations of current design</a><a class="headerlink" href="#limitations-of-current-design" title="Permalink to this headline">¶</a></h3>
<p>A Log record cannot span log files, and it must fit within a single
log buffer. Thus the size of a log record is limited by the size of
a log buffer and by the size of a log file. As a workaround to this
limitation, clients can split the data into multiple log records,
but in that case, clients are responsible for merging the data back
when reading from the Log.</p>
</div>
<div class="section" id="operations">
<h3><a class="toc-backref" href="#id80">Operations</a><a class="headerlink" href="#operations" title="Permalink to this headline">¶</a></h3>
<div class="section" id="creating-a-new-log-instance">
<h4><a class="toc-backref" href="#id81">Creating a new Log Instance</a><a class="headerlink" href="#creating-a-new-log-instance" title="Permalink to this headline">¶</a></h4>
<p>Several parameters must be supplied when creating a new log
instance. These are specified using a Java Properties object.</p>
<table border="1" class="docutils">
<colgroup>
<col width="37%" />
<col width="63%" />
</colgroup>
<thead valign="bottom">
<tr><th class="head">Property Name</th>
<th class="head">Description</th>
</tr>
</thead>
<tbody valign="top">
<tr><td><tt class="docutils literal"><span class="pre">log.ctl.{n}</span></tt></td>
<td>The fully qualified path to the
log control file. The first file should be specified as
<tt class="docutils literal"><span class="pre">log.ctl.1</span></tt>, second as <tt class="docutils literal"><span class="pre">log.ctl.2</span></tt>, and so on. Up to a
maximum of 3 can be specified. Default is 2.</td>
</tr>
<tr><td><tt class="docutils literal"><span class="pre">log.groups.{n}.path</span></tt></td>
<td>The path where log files of a group should be stored.
The first log group is specified as <tt class="docutils literal"><span class="pre">log.groups.1.path</span></tt>,
the second as <tt class="docutils literal"><span class="pre">log.groups.2.path</span></tt>,
and so on. Up to a maximum of 3 log groups can be
specified. Default number of groups is 1. Path defaults
to current directory.</td>
</tr>
<tr><td><tt class="docutils literal"><span class="pre">log.archive.path</span></tt></td>
<td>Defines the path for storing archive files. Defaults to
current directory.</td>
</tr>
<tr><td><tt class="docutils literal"><span class="pre">log.group.files</span></tt></td>
<td>Specifies the number of log files within each group.
Up to a maximum of 8 are allowed. Defaults to 2.</td>
</tr>
<tr><td><tt class="docutils literal"><span class="pre">log.file.size</span></tt></td>
<td>Specifies the size of each log file in
bytes. Default is 2 KB.</td>
</tr>
<tr><td><tt class="docutils literal"><span class="pre">log.buffer.size</span></tt></td>
<td>Specifies the size of the log buffer
in bytes. Default is 2 KB.</td>
</tr>
<tr><td><tt class="docutils literal"><span class="pre">log.buffer.limit</span></tt></td>
<td>Sets a limit on the maximum number of
log buffers that can be allocated. Default is 10 *
log.group.files.</td>
</tr>
<tr><td><tt class="docutils literal"><span class="pre">log.flush.interval</span></tt></td>
<td>Sets the interval (in seconds)
between log flushes. Default is 6 seconds.</td>
</tr>
<tr><td><tt class="docutils literal"><span class="pre">log.disableFlushRequests</span></tt></td>
<td>Boolean value, if set, disables
log flushes requested explicitly by the Buffer Manager
or Transaction Manager. Log flushes still occur during
checkpoints and log switches. By reducing the log flushes,
performance is improved, but transactions may not be
durable. Only those transactions will survive a system
crash that have all their log records on disk.</td>
</tr>
</tbody>
</table>
<p>Here is an example:</p>
<div class="highlight-python"><pre>LogFactory factory = new LogFactoryImpl();
Properties properties = new Properties();
properties.setProperty("log.ctl.1", "ctl.a");
properties.setProperty("log.ctl.2", "ctl.b");
properties.setProperty("log.groups.1.path", ".");
properties.setProperty("log.archive.path", ".");
properties.setProperty("log.group.files", "3");
properties.setProperty("log.file.size", "16384");
properties.setProperty("log.buffer.size", "16384");
properties.setProperty("log.buffer.limit", "4");
properties.setProperty("log.flush.interval", "30");
factory.createLog(properties);</pre>
</div>
</div>
<div class="section" id="opening-a-log-instance">
<h4><a class="toc-backref" href="#id82">Opening a log instance</a><a class="headerlink" href="#opening-a-log-instance" title="Permalink to this headline">¶</a></h4>
<p>Once a Log has been created, it can be opened for use. Opening the
log also starts back ground threads that handle periodic log flushes
and archival of log files. When the log is closed, the background
threads are shut down.</p>
<p>Following sample code shows how this is done:</p>
<div class="highlight-python"><pre>LogFactory factory = new LogFactoryImpl();
Properties properties = new Properties();
properties.setProperty("log.ctl.1", "ctl.a");
properties.setProperty("log.ctl.2", "ctl.b");
properties.setProperty("log.groups.1.path", ".");
properties.setProperty("log.archive.path", ".");
properties.setProperty("log.group.files", "3");
properties.setProperty("log.file.size", "16384");
properties.setProperty("log.buffer.size", "16384");
properties.setProperty("log.buffer.limit", "4");
properties.setProperty("log.flush.interval", "30");
LogMgr log = factory.openLog(properties);
try {
    // do some work
} finally {
    if (log != null)
        log.close();
}</pre>
</div>
<p>Note the use of finally block to ensure that the log is properly
closed.</p>
</div>
<div class="section" id="inserting-new-log-records">
<h4><a class="toc-backref" href="#id83">Inserting new log records</a><a class="headerlink" href="#inserting-new-log-records" title="Permalink to this headline">¶</a></h4>
<p>The Log Manager does not care about the contents of the log record.
It treats the contents as a byte stream. This is illustrated in the
following example:</p>
<div class="highlight-python"><pre>LogMgr log = factory.openLog(null);
try {
    String s = "hello world!";
    byte[] b = s.getBytes();
    Lsn lsn = log.insert(b, b.length);
} finally {
    if (log != null)
        log.close();
}</pre>
</div>
<p>Each new log record is assigned a unique sequence number known as
the Log Sequence Number (LSN). This can be used later on to retrieve
the log record.</p>
</div>
<div class="section" id="flushing-the-log">
<h4><a class="toc-backref" href="#id84">Flushing the Log</a><a class="headerlink" href="#flushing-the-log" title="Permalink to this headline">¶</a></h4>
<p>When new log records are created, initially they are stored in the
Log Buffers. The log records are flushed to disk either upon request
or by the background thread that periodically flushes the Log.
Clients can request the log to be flushed upto a specified LSN. Note
that this is a blocking call, i.e., the client will be blocked until
the flush is completed.</p>
<p>Example:</p>
<div class="highlight-python"><pre>String s = "hello world!";
byte[] b = s.getBytes();
Lsn lsn = log.insert(b, b.length);
log.flush(lsn);</pre>
</div>
<p>Typically, flush requests are issued by Transaction Manager, when a
transaction commits or aborts, or by the Buffer Manager when it is
about to write a dirty buffer.</p>
</div>
<div class="section" id="reading-log-records">
<h4><a class="toc-backref" href="#id85">Reading Log records</a><a class="headerlink" href="#reading-log-records" title="Permalink to this headline">¶</a></h4>
<p>Log records can be read individually or using a scan. The Log
Manager allows both forward and backward scans of the Log. A
starting LSN can be specified; if this is not specified then the
scanning will begin from the first or last record, depending upon
whether it is a forward or backward scan.</p>
<p>Shown below is an example of directly accessing a log record by its
LSN:</p>
<div class="highlight-python"><pre>Lsn myLsn = ...;
LogRecord logrec = log.read(myLsn);
byte[] data = logrec.getData();</pre>
</div>
<p>Shown below is an example of using the Log Scan facility:</p>
<div class="highlight-python"><pre>void readAllRecords(LogMgr log) throws Exception {
    LogReader reader = log.getForwardScanningReader(null);
    try {
        for (;;) {
            LogRecord rec = reader.getNext();
            if (rec == null) {
                break;
            }
            printRecord(rec);
        }
    }
    finally {
        if (reader != null)
            reader.close();
    }
}</pre>
</div>
</div>
<div class="section" id="checkpoint-records">
<h4><a class="toc-backref" href="#id86">Checkpoint Records</a><a class="headerlink" href="#checkpoint-records" title="Permalink to this headline">¶</a></h4>
<p>In transactional systems there is often a need to maintain special
checkpoint records that contain a snapshot of the system at a point
in time. Checkpoint records can be handled in the same way as normal
log records, however, the Log Manager also maintains information
about the most recent checkpoint record. Whenever a checkpoint
record is written, the Log Manager should be informed about its LSN.
This ensures that at the next flush, the Log Control files are
updated.</p>
<div class="highlight-python"><pre>CheckpointRecord checkpointRec = new CheckpointRecord();
Lsn checkpointLsn = log.insert(checkpointRec.getData(),
        checkpointRec.getLength());
logmgr.setCheckpointLsn(checkpointLsn);
logmgr.flush(checkpointLsn);</pre>
</div>
<p>The LSN of the last checkpoint record can be retrieved at any time
using the getCheckpointLsn() method. Note that if the Checkpoint
Record is too large and needs to be broken up into smaller records,
then the checkpointLsn should be set to the first checkpoint record.</p>
</div>
</div>
</div>
<div class="section" id="lock-manager">
<h2><a class="toc-backref" href="#id87">Lock Manager</a><a class="headerlink" href="#lock-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id6">
<h3><a class="toc-backref" href="#id88">Introduction</a><a class="headerlink" href="#id6" title="Permalink to this headline">¶</a></h3>
<p>All multi-user transactional systems use some form of locking to
ensure that concurrent transactions do not conflict with each other.
Depending upon the level of consistency guaranteed by the
transactional system the number and type of locks used can vary.</p>
<p>In a single user system, no locking is needed. Transaction are
automatically consistent, as only one transaction can execute at any
point in time.</p>
</div>
<div class="section" id="locking-basics">
<h3><a class="toc-backref" href="#id89">Locking Basics</a><a class="headerlink" href="#locking-basics" title="Permalink to this headline">¶</a></h3>
<p>In multi-user systems, transactions must be allowed to proceed
concurrently if reasonable performance is to be obtained. However,
this means that unless some form of locking is used, data
consistency problems will arise. For example, if two transactions
update the same record at the same time, one of the updates may be
lost.</p>
<p>To prevent this sort of thing from happening, each transaction must
lock the data that it updates or reads. A lock is a mechanism by
which access to the record is restricted to the transaction that
owns the lock. Furthermore, a lock restricts the type of operation
that is permitted to occur. For example, a Shared lock can be owned
by multiple transactions concurrently and allows read operations. An
Exclusive lock permits both read and write operations but can only
be granted to one transaction at any point on time. Moreover Shared
locks and Exclusive locks are incompatible; this means that if a
Shared Lock is held by a transaction on a record, another
transaction cannot obtain an Exclusive lock on the same record, and
vice-versa.</p>
</div>
<div class="section" id="two-phase-locking-and-repeatable-read-isolation-level">
<h3><a class="toc-backref" href="#id90">Two-Phase Locking and Repeatable Read Isolation Level</a><a class="headerlink" href="#two-phase-locking-and-repeatable-read-isolation-level" title="Permalink to this headline">¶</a></h3>
<p>Not only must a record be locked when it is updated, the transaction
must hold the lock until the transaction is committed or aborted.
This strategy leads to the basic rule of two-phase locking, which
requires that a transaction must manage its locks in two distinct
phases. In the first phase, the transaction is permitted to acquire
locks, but cannot release any locks. The first phase lasts right up
to the moment the transaction is completed, i.e., either committed
or aborted. In the second phase, when the transaction is committed
or aborted, all locks are released. No further locks can be acquired
in this phase. Strict two phase locking ensures that despite
concurrent running of transactions, each transaction has the
appearance of running in isolation. Strict two-phase locking
strategy provides a level of consistency called Repeatable Read.</p>
</div>
<div class="section" id="read-committed-isolation-level">
<h3><a class="toc-backref" href="#id91">Read Committed Isolation Level</a><a class="headerlink" href="#read-committed-isolation-level" title="Permalink to this headline">¶</a></h3>
<p>This basic strategy can be modified to obtain greater concurrency at
the cost of data consistency. For example, read locks can be
released early to allow other transactions to read data. While this
increases concurrency, it does mean that reads are not repeatable,
because the original transaction may find that the data it read
previously has been modified by the time it is read a second time.
This level of consistency is known as Read Committed.</p>
</div>
<div class="section" id="serializable-isolation-level">
<h3><a class="toc-backref" href="#id92">Serializable Isolation Level</a><a class="headerlink" href="#serializable-isolation-level" title="Permalink to this headline">¶</a></h3>
<p>Although the Repeatable Read level of consistency prevents data that
has been read by one transaction from being modified by another, it
does not prevent the problem of phantom reads, which occurs when new
records are inserted. For example, if a range of records is read
twice by the same transaction, and another transaction has inserted
new records in the time interval between the two reads, then the
second read will encounter records that did not appear the first
time. To prevent this type of phantom reads from occurring, locking
has to be made even more comprehensive. Rather than locking one
record, certain operations need to lock entire ranges of records,
even non-existent ones. This is typically achieved using a logical
convention; a lock on a particular data item represents not only a
lock on that data, but also the range of data up to and including
the data item being locked. For example, if there are two records A
and C, then a lock on C would encompass the entire range of data
between A and C, excluding A, but including and up to C.</p>
</div>
<div class="section" id="design-choices">
<h3><a class="toc-backref" href="#id93">Design choices</a><a class="headerlink" href="#design-choices" title="Permalink to this headline">¶</a></h3>
<p>The Locking subsystem specified in <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> requires that locks
should be implemented independently of the objects being locked. In
order for locking to work, all participants must agree to agree to
use the locking system and abide by the rules.</p>
<p>Another design constraint is that the interface is geared towards a
memory based implementation. This places a constraint on the number
of locks that can be held within the system, because a large number
of locks would require a prohibitively large amount of memory.</p>
<p>Some database systems, Oracle, in particular, use markers within the
databases disk pages to represent locks. A lock byte is used, for
instance, to denote whether a row is locked or not. The advantage of
Oracle&#8217;s approach is that there are no constraints on the number of
locks the system can handle. The disadvantage is that the lock
status is maintained in persistent storage, therefore changing the
lock status can make a page dirty. Oracle overcomes this issue in
two ways. Firstly, it uses a multi-version system that does not
require read locks. Thus, locks are used only for updates, and
since updates cause database pages to be touched anyway, using a
lock status byte does not pose a problem. Secondly, Oracle avoids
updating the lock status byte when locks are released, by using
information about the transaction status to infer that a lock has
been released.</p>
<p>The interface for the Locking System specified in this package does
not support implementations of the type used in Oracle.</p>
<p>In some systems, locking is based upon facilities provided by the
underlying operating system. For instance, most operating systems
support some form of file locking. Since database records are laid
out into regions within a file system, file system locks can be
applied on records. This is not the best way of implementing locks.
This is because locking a region in the file would prevent all
access to that region, which would cause other problems. Even when
systems do use file system locks, typically, some form of logical
locking is used. For example, in DBASE III based systems, a single
byte in the file represents a record lock. In general, relying upon
file system locks can be source of numerous problems, such as
portability of the system, performance, etc.</p>
</div>
<div class="section" id="lock-modes">
<h3><a class="toc-backref" href="#id94">Lock Modes</a><a class="headerlink" href="#lock-modes" title="Permalink to this headline">¶</a></h3>
<p>The <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> Lock Manager supports the following Lock Modes:</p>
<dl class="docutils">
<dt>INTENTION_SHARED</dt>
<dd>Indicates the intention to read data at a lower level of
granularity.</dd>
<dt>INTENTION_EXCLUSIVE</dt>
<dd>Indicates the intention to update data at a lower level of
granularity.</dd>
<dt>SHARED</dt>
<dd>Permits readers.</dd>
<dt>SHARED_INTENTION_EXCLUSIVE</dt>
<dd>Indicates SHARED lock at current level and intention to update
data at a lower level of granularity.</dd>
<dt>UPDATE</dt>
<dd>Indicates intention to update, Permits readers.</dd>
<dt>EXCLUSIVE</dt>
<dd>Prevents access by other users.</dd>
</dl>
<div class="section" id="lock-compatibility-matrix">
<h4><a class="toc-backref" href="#id95">Lock Compatibility Matrix</a><a class="headerlink" href="#lock-compatibility-matrix" title="Permalink to this headline">¶</a></h4>
<p>The lock compatibility matrix for above is given below:</p>
<table border="1" class="docutils">
<caption>Lock Compatibility Table</caption>
<colgroup>
<col width="20%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
</colgroup>
<thead valign="bottom">
<tr><th class="head">Mode</th>
<th class="head">NONE</th>
<th class="head">IS</th>
<th class="head">IX</th>
<th class="head">S</th>
<th class="head">SIX</th>
<th class="head">U</th>
<th class="head">X</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>NONE</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
</tr>
<tr><td>Intent
Shared</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
<td>N</td>
<td>N</td>
</tr>
<tr><td>Intent
Exclusive</td>
<td>Y</td>
<td>Y</td>
<td>Y</td>
<td>N</td>
<td>N</td>
<td>N</td>
<td>N</td>
</tr>
<tr><td>Shared</td>
<td>Y</td>
<td>Y</td>
<td>N</td>
<td>Y</td>
<td>N</td>
<td>N</td>
<td>N</td>
</tr>
<tr><td>Shared
Intent
Excluive</td>
<td>Y</td>
<td>Y</td>
<td>N</td>
<td>N</td>
<td>N</td>
<td>N</td>
<td>N</td>
</tr>
<tr><td>Update</td>
<td>Y</td>
<td>N</td>
<td>N</td>
<td>Y</td>
<td>N</td>
<td>N</td>
<td>N</td>
</tr>
<tr><td>Exclusive</td>
<td>Y</td>
<td>N</td>
<td>N</td>
<td>N</td>
<td>N</td>
<td>N</td>
<td>N</td>
</tr>
</tbody>
</table>
</div>
<div class="section" id="lock-conversions">
<h4><a class="toc-backref" href="#id96">Lock Conversions</a><a class="headerlink" href="#lock-conversions" title="Permalink to this headline">¶</a></h4>
<p><a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>&#8216;s Lock Manager also supports Lock Conversions. The
following table shows how lock conversions are handled:</p>
<table border="1" class="docutils">
<caption>Lock Conversion Table</caption>
<colgroup>
<col width="20%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
<col width="11%" />
</colgroup>
<thead valign="bottom">
<tr><th class="head">Mode</th>
<th class="head">NONE</th>
<th class="head">IS</th>
<th class="head">IX</th>
<th class="head">S</th>
<th class="head">SIX</th>
<th class="head">U</th>
<th class="head">X</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>NONE</td>
<td>NONE</td>
<td>IS</td>
<td>IX</td>
<td>S</td>
<td>SIX</td>
<td>U</td>
<td>X</td>
</tr>
<tr><td>Intent
Shared</td>
<td>IS</td>
<td>IS</td>
<td>IX</td>
<td>S</td>
<td>SIX</td>
<td>U</td>
<td>X</td>
</tr>
<tr><td>Intent
Exclusive</td>
<td>IX</td>
<td>IX</td>
<td>IX</td>
<td>SIX</td>
<td>SIX</td>
<td>X</td>
<td>X</td>
</tr>
<tr><td>Shared</td>
<td>S</td>
<td>S</td>
<td>SIX</td>
<td>S</td>
<td>SIX</td>
<td>U</td>
<td>X</td>
</tr>
<tr><td>Shared
Intent
Exclusive</td>
<td>SIX</td>
<td>SIX</td>
<td>SIX</td>
<td>SIX</td>
<td>SIX</td>
<td>SIX</td>
<td>X</td>
</tr>
<tr><td>Update</td>
<td>U</td>
<td>U</td>
<td>X</td>
<td>U</td>
<td>SIX</td>
<td>U</td>
<td>X</td>
</tr>
<tr><td>Exclusive</td>
<td>X</td>
<td>X</td>
<td>X</td>
<td>X</td>
<td>X</td>
<td>X</td>
<td>X</td>
</tr>
</tbody>
</table>
</div>
</div>
<div class="section" id="id7">
<h3><a class="toc-backref" href="#id97">Operations</a><a class="headerlink" href="#id7" title="Permalink to this headline">¶</a></h3>
<div class="section" id="obtaining-an-instance-of-lock-manager">
<h4><a class="toc-backref" href="#id98">Obtaining an instance of Lock Manager</a><a class="headerlink" href="#obtaining-an-instance-of-lock-manager" title="Permalink to this headline">¶</a></h4>
<p><a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> provides a factory class for generating instances of the
Lock Manager. Note that locks are meaningful only within an instance
of the Lock Manager &#8211; if there are two Lock Manager instances, each
will have its own set of locks.</p>
<p>Following sample code shows how to obtain an instance of the Lock
Manager.</p>
<div class="highlight-python"><pre>LockMgrFactory factory = new LockMgrFactoryImpl();
Properties props = new Properties();
LockMgr lockmgr = factory.create(props);</pre>
</div>
<p>The only property that can be set is the Hash Table size.</p>
</div>
<div class="section" id="lockable-objects">
<h4><a class="toc-backref" href="#id99">Lockable objects</a><a class="headerlink" href="#lockable-objects" title="Permalink to this headline">¶</a></h4>
<p>Any object can be locked. The only requirement is that the object
should implement the <tt class="docutils literal"><span class="pre">hashCode()</span></tt> and <tt class="docutils literal"><span class="pre">equals()</span></tt> methods.
For the system to work correctly, lockable objects should be
immutable &#8211; once created they must not be modified. Clearly, if the
object is modified while it is referenced in the lock tables, then
the system will malfunction, as the object will no longer respond to
<tt class="docutils literal"><span class="pre">hashCode()</span></tt> and <tt class="docutils literal"><span class="pre">equals()</span></tt> in a consistent manner.</p>
</div>
<div class="section" id="lock-owners">
<h4><a class="toc-backref" href="#id100">Lock Owners</a><a class="headerlink" href="#lock-owners" title="Permalink to this headline">¶</a></h4>
<p>Every lock must have an owner. The LockMgr interface allows any
object to be lock owner; the only requirement is that the object
must implement the <tt class="docutils literal"><span class="pre">equals()</span></tt> method.</p>
</div>
<div class="section" id="lock-durations">
<h4><a class="toc-backref" href="#id101">Lock Durations</a><a class="headerlink" href="#lock-durations" title="Permalink to this headline">¶</a></h4>
<p>Locks can be acquired for an <tt class="docutils literal"><span class="pre">INSTANT_DURATION</span></tt> or
<tt class="docutils literal"><span class="pre">MANUAL_DURATION</span></tt>. Instant duration locks are not acquired in
reality &#8211; the caller is delayed until the lock becomes available.
Manual duration locks are held until they are released. Such locks
have a reference count attached to them. If the lock is acquired
more than once, the reference count is incremented. The lock will
not be released until the reference count becomes zero.</p>
<p>Typically, a Transaction will hold locks until the transaction ends.
In some cases, SHARED locks may be released early, for example, in
the READ COMMITTED Isolation Level.</p>
</div>
<div class="section" id="acquiring-and-releasing-locks">
<h4><a class="toc-backref" href="#id102">Acquiring and releasing locks</a><a class="headerlink" href="#acquiring-and-releasing-locks" title="Permalink to this headline">¶</a></h4>
<p>Locks can be acquired using the <tt class="docutils literal"><span class="pre">acquire()</span></tt> method provided by
the LockMgr interface. The acquire method returns a Handle to the
lock, which can be used subsequently to release the lock. Example:</p>
<div class="highlight-python"><pre>LockMgr lockmgr = new LockMgrImpl(71);
Object owner = new Integer(1);
Object lockname = new Integer(10);
LockHandle handle = lockmgr.acquire(owner, lockname,
    LockMode.EXCLUSIVE, LockDuration.MANUAL_DURATION, -1);
// do some work
handle.release(false);</pre>
</div>
</div>
<div class="section" id="algorithm">
<h4><a class="toc-backref" href="#id103">Algorithm</a><a class="headerlink" href="#algorithm" title="Permalink to this headline">¶</a></h4>
<p>The main algorithm for the lock manager is shown in the form of use cases.
The description here is inspired by a similar description in <a class="reference internal" href="#cockburn">[COCKBURN]</a>.</p>
<div class="section" id="a001-lock-acquire">
<h5><a class="toc-backref" href="#id104">a001 - lock acquire</a><a class="headerlink" href="#a001-lock-acquire" title="Permalink to this headline">¶</a></h5>
<div class="section" id="main-success-scenario">
<h6><a class="toc-backref" href="#id105">Main Success Scenario</a><a class="headerlink" href="#main-success-scenario" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li>Search for the lock header</li>
<li>Lock header not found</li>
<li>Allocate new lock header</li>
<li>Allocate new lock request</li>
<li>Append lock request to queue with status = GRANTED and reference count of 1.</li>
<li>Set lock granted mode to GRANTED</li>
</ol>
</div>
<div class="section" id="extensions">
<h6><a class="toc-backref" href="#id106">Extensions</a><a class="headerlink" href="#extensions" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple" start="2">
<li><ol class="first loweralpha">
<li>Lock header found but client has no prior request for the lock.<ol class="arabic">
<li>Do <a class="reference internal" href="#a003-handle-new-request">a003 - handle new request</a>.</li>
</ol>
</li>
<li>Lock header found and client has a prior GRANTED lock request.<ol class="arabic">
<li>Do <a class="reference internal" href="#a002-handle-lock-conversion">a002 - handle lock conversion</a>.</li>
</ol>
</li>
</ol>
</li>
</ol>
</div>
</div>
<div class="section" id="a003-handle-new-request">
<h5><a class="toc-backref" href="#id107">a003 - handle new request</a><a class="headerlink" href="#a003-handle-new-request" title="Permalink to this headline">¶</a></h5>
<div class="section" id="id9">
<h6><a class="toc-backref" href="#id108">Main Success Scenario</a><a class="headerlink" href="#id9" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li>Allocate new request.</li>
<li>Append lock request to queue with reference count of 1.</li>
<li>Check for waiting requests.</li>
<li>Check whether request is compatible with granted mode.</li>
<li>There are no waiting requests and lock request is compatible with
granted mode.</li>
<li>Set lock&#8217;s granted mode to maximum of this request and existing granted mode.</li>
<li>Success.</li>
</ol>
</div>
<div class="section" id="id10">
<h6><a class="toc-backref" href="#id109">Extensions</a><a class="headerlink" href="#id10" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple" start="5">
<li><ol class="first loweralpha">
<li>There are waiting requests or lock request is not compatible with
granted mode.<ol class="arabic">
<li>Do <a class="reference internal" href="#a004-lock-wait">a004 - lock wait</a>.</li>
</ol>
</li>
</ol>
</li>
</ol>
</div>
</div>
<div class="section" id="a002-handle-lock-conversion">
<h5><a class="toc-backref" href="#id110">a002 - handle lock conversion</a><a class="headerlink" href="#a002-handle-lock-conversion" title="Permalink to this headline">¶</a></h5>
<div class="section" id="id11">
<h6><a class="toc-backref" href="#id111">Main Success Scenario</a><a class="headerlink" href="#id11" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li>Check lock compatibility with granted group.</li>
<li>Lock request is compatible with granted group.</li>
<li>Grant lock request, and update granted mode for the request.</li>
</ol>
</div>
<div class="section" id="id12">
<h6><a class="toc-backref" href="#id112">Extensions</a><a class="headerlink" href="#id12" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple" start="2">
<li><ol class="first loweralpha">
<li>Lock request is incompatible with granted group.<ol class="arabic">
<li>Do <a class="reference internal" href="#a004-lock-wait">a004 - lock wait</a>.</li>
</ol>
</li>
</ol>
</li>
</ol>
</div>
</div>
<div class="section" id="a004-lock-wait">
<h5><a class="toc-backref" href="#id113">a004 - lock wait</a><a class="headerlink" href="#a004-lock-wait" title="Permalink to this headline">¶</a></h5>
<div class="section" id="id13">
<h6><a class="toc-backref" href="#id114">Main Success Scenario</a><a class="headerlink" href="#id13" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li>Wait for lock.</li>
<li>Lock granted.</li>
<li>Success.</li>
</ol>
</div>
<div class="section" id="id14">
<h6><a class="toc-backref" href="#id115">Extensions</a><a class="headerlink" href="#id14" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple" start="2">
<li><ol class="first loweralpha">
<li>Lock was not granted.<ol class="arabic">
<li>Failure!</li>
</ol>
</li>
</ol>
</li>
</ol>
</div>
</div>
<div class="section" id="b001-release-lock">
<h5><a class="toc-backref" href="#id116">b001 - release lock</a><a class="headerlink" href="#b001-release-lock" title="Permalink to this headline">¶</a></h5>
<div class="section" id="id15">
<h6><a class="toc-backref" href="#id117">Main Success Scenario</a><a class="headerlink" href="#id15" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li>Decrease reference count.</li>
<li>Sole lock request and reference count is zero.</li>
<li>Remove lock header from hash table.</li>
<li>Success.</li>
</ol>
</div>
<div class="section" id="id16">
<h6><a class="toc-backref" href="#id118">Extensions</a><a class="headerlink" href="#id16" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple" start="2">
<li><ol class="first loweralpha">
<li>Reference count greater than zero.<ol class="arabic">
<li>Success.</li>
</ol>
</li>
</ol>
</li>
</ol>
<ol class="arabic simple" start="2">
<li><ol class="first loweralpha" start="2">
<li>Reference count is zero and there are other requests on the lock.<ol class="arabic">
<li>Remove request from the queue.</li>
<li>Do <a class="reference internal" href="#b002-grant-waiters">b002 - grant waiters</a>.</li>
</ol>
</li>
</ol>
</li>
</ol>
</div>
</div>
<div class="section" id="b002-grant-waiters">
<h5><a class="toc-backref" href="#id119">b002 - grant waiters</a><a class="headerlink" href="#b002-grant-waiters" title="Permalink to this headline">¶</a></h5>
<div class="section" id="id17">
<h6><a class="toc-backref" href="#id120">Main Success Scenario</a><a class="headerlink" href="#id17" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li>Get next granted lock.</li>
<li>Recalculate granted mode.</li>
<li>Repeat from 1) until no more granted requests.</li>
<li>Get next waiting request.</li>
<li>Request is compatible with granted mode.</li>
<li>Grant request and wake up thread waiting for the lock. Increment reference count of
the granted request and set granted mode to maximum of current mode and granted request.</li>
<li>Repeat from 4) until no more waiting requests.</li>
</ol>
</div>
<div class="section" id="id18">
<h6><a class="toc-backref" href="#id121">Extensions</a><a class="headerlink" href="#id18" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li><ol class="first loweralpha">
<li>Conversion request.<ol class="arabic">
<li>Do <a class="reference internal" href="#b003-grant-conversion-request">b003 - grant conversion request</a>.</li>
<li>Resume from 2).</li>
</ol>
</li>
</ol>
</li>
</ol>
<ol class="arabic simple" start="4">
<li><ol class="first loweralpha">
<li>&#8220;conversion pending&#8221; is set (via b003).<ol class="arabic">
<li>Done.</li>
</ol>
</li>
</ol>
</li>
<li><ol class="first loweralpha">
<li>Request is incompatible with granted mode.<ol class="arabic">
<li>Done.</li>
</ol>
</li>
</ol>
</li>
</ol>
</div>
</div>
<div class="section" id="b003-grant-conversion-request">
<h5><a class="toc-backref" href="#id122">b003 - grant conversion request</a><a class="headerlink" href="#b003-grant-conversion-request" title="Permalink to this headline">¶</a></h5>
<div class="section" id="id19">
<h6><a class="toc-backref" href="#id123">Main Success Scenario</a><a class="headerlink" href="#id19" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li>Do <a class="reference internal" href="#c001-check-request-compatible-with-granted-group">c001 - check request compatible with granted group</a>.</li>
<li>Request is compatible.</li>
<li>Grant conversion request.</li>
</ol>
</div>
<div class="section" id="id20">
<h6><a class="toc-backref" href="#id124">Extensions</a><a class="headerlink" href="#id20" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple" start="2">
<li><ol class="first loweralpha">
<li>Conversion request incompatible with granted group.<ol class="arabic">
<li>Set &#8220;conversion pending&#8221; flag.</li>
</ol>
</li>
</ol>
</li>
</ol>
</div>
</div>
<div class="section" id="c001-check-request-compatible-with-granted-group">
<h5><a class="toc-backref" href="#id125">c001 - check request compatible with granted group</a><a class="headerlink" href="#c001-check-request-compatible-with-granted-group" title="Permalink to this headline">¶</a></h5>
<div class="section" id="id21">
<h6><a class="toc-backref" href="#id126">Main Success Scenario</a><a class="headerlink" href="#id21" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li>Get next granted request.</li>
<li>Request is compatible with this request.</li>
<li>Repeat from 1) until no more granted requests.</li>
</ol>
</div>
<div class="section" id="id22">
<h6><a class="toc-backref" href="#id127">Extensions</a><a class="headerlink" href="#id22" title="Permalink to this headline">¶</a></h6>
<ol class="arabic simple">
<li><ol class="first loweralpha">
<li>Request belongs to the caller.<ol class="arabic">
<li>Resume from step 3).</li>
</ol>
</li>
</ol>
</li>
<li><ol class="first loweralpha">
<li>Request is incompatible with this request.<ol class="arabic">
<li>Failure!</li>
</ol>
</li>
</ol>
</li>
</ol>
</div>
</div>
</div>
<div class="section" id="data-structures-of-the-lock-manager">
<h4><a class="toc-backref" href="#id128">Data Structures of the Lock Manager</a><a class="headerlink" href="#data-structures-of-the-lock-manager" title="Permalink to this headline">¶</a></h4>
<p>The Lock Manager data structures are based upon the structures described in
<a class="reference internal" href="#jgray">[JGRAY]</a>. A hash table is used to maintain a lookup table for finding lock
objects. The buckets in the hash table point to linked lists of lock headers.
Each lock header holds housekeeping information about a single lock. A chain of
lock requests is attached to the lock header. Each request represents a lock
request by a client. At any point in time, a lock may have multiple requests
queuing - some in GRANTED state, others waiting for the lock to be GRANTED.</p>
<p>The data structure used by the Lock Manager is depicted below.</p>
<img alt="_images/lock-table.jpg" src="_images/lock-table.jpg" />
</div>
<div class="section" id="deadlock-detector">
<h4><a class="toc-backref" href="#id129">Deadlock Detector</a><a class="headerlink" href="#deadlock-detector" title="Permalink to this headline">¶</a></h4>
<p>The Lock Manager contains a simple Deadlock Detector implemented
which is based upon algorithm described in <a class="reference internal" href="#jgray">[JGRAY]</a>. The deadlock
detector runs in a background thread, periodically waking up to
check for deadlocks. When a deadlock is detected, one of the transactions
(chosen arbitrarily) is aborted.</p>
</div>
</div>
</div>
<div class="section" id="page-manager">
<h2><a class="toc-backref" href="#id130">Page Manager</a><a class="headerlink" href="#page-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="overview-of-page-manager-module">
<h3><a class="toc-backref" href="#id131">Overview of Page Manager module</a><a class="headerlink" href="#overview-of-page-manager-module" title="Permalink to this headline">¶</a></h3>
<p>The storage unit of a database system is a Page. In SimpleDBM, pages
are contained with logical units called Storage Containers. The default
implementation maps containers to Operating System files.</p>
<p>A page is typically a fixed size block within the storage container.
The PageManager module encapsulates knowledge about how pages
map to containers. It knows about the page size, but delegates the work of
reading/writing pages to PageFactory implementations. This division of labour
allows all pages to be centrally managed by the PageManager, yet allows
new page types to be registered without having to change the PageManager.
By isolating the management of pages into the PageManager module,
the rest of the system is protected. For example, the BufferManager module can work with
different paging strategies by switching the PageManager module.</p>
<p>Note that the PageManager module does not worry about the contents
of the page, except for the very basic and common stuff that must be
part of every page, such as a checksum, the page Id, page LSN, and
the page type. It is expected that other modules will extend the basic page type and
implement additional features. The PageManager does provide the
base class for all Page implementations.</p>
</div>
<div class="section" id="interactions-with-other-modules">
<h3><a class="toc-backref" href="#id132">Interactions with other modules</a><a class="headerlink" href="#interactions-with-other-modules" title="Permalink to this headline">¶</a></h3>
<p>The Buffer Manager module uses the PageManager module to read/write
pages from storage containers and also to create new instances of
pages.</p>
<p>The PageManager module requires the services of the Object Registry
module in order to obtain PageFactory implementations.</p>
<p>The PageManager uses PageFactory implementations to read/write pages.</p>
<p>The PageManager module also interacts with the StorageManager module
for access to Storage Containers.</p>
<p>Each page is allocated a Latch to manage concurrent access to it.
The PageManager therefore requires the services of the Latch
Manager.</p>
</div>
<div class="section" id="page-class">
<h3><a class="toc-backref" href="#id133">Page class</a><a class="headerlink" href="#page-class" title="Permalink to this headline">¶</a></h3>
<p>The page manager provides an abstract Page class that is the root
of the Page hierarchy. All other page types derive from this class.
The simplest of Page classes that one could create is shown below:</p>
<div class="highlight-python"><pre>public final class RawPage extends Page {
  RawPage(PageManager pageFactory, int type, PageId pageId) {
    super(pageFactory, type, pageId);
  }
  RawPage(PageManager pageFactory, PageId pageId, ByteBuffer bb) {
    super(pageFactory, pageId, bb);
  }
}</pre>
</div>
<p>The constructor that accepts the ByteBuffer argument, should
retrieve the contents of the Page from the ByteBuffer.</p>
<div class="section" id="page-size-and-implementation-of-storable-interface">
<h4><a class="toc-backref" href="#id134">Page Size and implementation of Storable interface</a><a class="headerlink" href="#page-size-and-implementation-of-storable-interface" title="Permalink to this headline">¶</a></h4>
<p>The Page class implements the Storable interface. However, unlike
other implementations, a Page has a fixed length which is defined by
the PageManager responsible for creating it. The Page obtains the
page size from the PageManager instance and uses that to determine
its persistent size. Sub-classes cannot change this value. This
means that the page size of all pages managed by a particular
PageManager instance is always the same.</p>
<p>Sub-classes of course still need to implement their own store() method
and a constructor that can initialize the object from a supplied
ByteBuffer object. These methods should always invoke their super
class counterparts before processing local content.</p>
<p>Example:</p>
<div class="highlight-python"><pre>public class MyPage extends Page {
     int i = 0;

  MyPage(PageManager pageFactory, int type, PageId pageId) {
    super(pageFactory, type, pageId);
  }

  MyPage(PageManager pageFactory, PageId pageId, ByteBuffer bb) {
    super(pageFactory, pageId, bb);
    i = bb.getInt();
  }

  /**
   * @see org.simpledbm.rss.api.pm.Page#store(java.nio.ByteBuffer)
   */
  @Override
  public void store(ByteBuffer bb) {
    super.store(bb);
    bb.putInt(i);
  }
}</pre>
</div>
</div>
<div class="section" id="how-various-page-types-are-managed">
<h4><a class="toc-backref" href="#id135">How various Page types are managed</a><a class="headerlink" href="#how-various-page-types-are-managed" title="Permalink to this headline">¶</a></h4>
<p>Some of the SimpleDBM modules define their own page types. These page types
are not known to the BufferManager or the TransactionManager, which must
still handle such pages, even read and write them to the disk as
necessary. This is made possible as follows:</p>
<ul class="simple">
<li>Each Page type is given a typecode in the Object Registry. A PageFactory
implementation is registered for each Page typecode.</li>
<li>The typecode is stored in the first two bytes (as a short
integer) of the Page when the page is persisted. When reading
a page, the first two bytes are inspected to determine the
correct Page type to instantiate. Reading and writing various
page types is managed by the PageFactory implementation.</li>
<li>The PageManager looks up the PageFactory implementation in the
ObjectRegistry, whenever it needs to persist or read pages.</li>
<li>The Buffer Manager uses the PageManager to
generate new instances of Pages or to read/write specific
pages.</li>
<li>The abstract Page class provides a common interface for
all Pages. This interface implements all the functionality
that is required by the Transaction Manager module to manage
updates to pages.</li>
</ul>
</div>
<div class="section" id="page-factory">
<h4><a class="toc-backref" href="#id136">Page Factory</a><a class="headerlink" href="#page-factory" title="Permalink to this headline">¶</a></h4>
<p>Creating a page factory is relatively simple:</p>
<div class="highlight-python"><pre>static class MyPageFactory implements PageFactory {

  final PageManager pageManager;

  public MyPageFactory(PageManager pageManager) {
    this.pageManager = pageManager;
  }
  public Page getInstance(int type, PageId pageId) {
    return new MyPage(pageManager, type, pageId);
  }
  public Page getInstance(PageId pageId, ByteBuffer bb) {
    return new MyPage(pageManager, pageId, bb);
  }
  public int getPageType() {
    return TYPE_MYPAGE;
  }
}</pre>
</div>
<p>Note that the PageFactory implementation passes on the
PageManager reference to new pages.</p>
<p>The PageFactory provide two methods for creating new instances
of Pages. The first method creates an empty Page. The second creates a
Page instance by reading the contents of a ByteBuffer - this method is
used when pages are read from a StorageContainer.</p>
<p>The PageFactory implementation must be registered with the
ObjectRegistry as a Singleton:</p>
<div class="highlight-python"><pre>static final short TYPE_MYPAGE = 25000;
ObjectRegistry objectRegistry = ...;
objectRegistry.registerSingleton(TYPE_MYPAGE, new MyPage.MyPageFactory(pageFactory));</pre>
</div>
</div>
<div class="section" id="id25">
<h4><a class="toc-backref" href="#id137">Page Manager</a><a class="headerlink" href="#id25" title="Permalink to this headline">¶</a></h4>
<p>Following snippet of code shows how the PageManager instance is created:</p>
<div class="highlight-python"><pre>Properties properties = new Properties();
properties.setProperty("storage.basePath", "testdata/TestPage");
properties.setProperty("logging.properties.file", "classpath:simpledbm.logging.properties");
properties.setProperty("logging.properties.type", "log4j");
platform = new PlatformImpl(properties);
storageFactory = new FileStorageContainerFactory(platform,
  properties);
objectRegistry = new ObjectRegistryImpl(platform, properties);
storageManager = new StorageManagerImpl(platform, properties);
latchFactory = new LatchFactoryImpl(platform, properties);
pageManager = new PageManagerImpl(
  platform,
  objectRegistry,
  storageManager,
  latchFactory,
  properties);</pre>
</div>
<p>Note that the PageManager requires access to the ObjectRegistry,
the LatchManager and the StorageManager. PageFactory instances are
retrieved indirectly via the ObjectRegistry.</p>
</div>
<div class="section" id="storing-and-retrieving-pages">
<h4><a class="toc-backref" href="#id138">Storing and retrieving Pages</a><a class="headerlink" href="#storing-and-retrieving-pages" title="Permalink to this headline">¶</a></h4>
<p>Before pages can be stored or retrieved, the appropriate Storage
Containers must be created/opened and registered with the Storage
Manager. Also, the Page types must be registered with the Object
Registry. Following sample code shows how this may be done:</p>
<div class="highlight-python"><pre>String name = "testfile.dat";
// Create a new storage container called testfile.dat
StorageContainer sc = storageFactory.create(name);
// Assign it a container ID of 1
storageManager.register(1, sc);
// Register the Page Type
objectFactory.register("mypage", TYPE_MYPAGE, MyPage.class.getName());
// Create a new instance of the page
MyPage page = (MyPage) pageFactory.getInstance("mypage", new PageId(1,
    0));
// Store the page in the container
pageFactory.store(page);
// Retrieve the page from the container
page = (MyPage) pageFactory.retrieve(new PageId(1, 0));</pre>
</div>
</div>
<div class="section" id="checksum">
<h4><a class="toc-backref" href="#id139">Checksum</a><a class="headerlink" href="#checksum" title="Permalink to this headline">¶</a></h4>
<p>When a page is persisted, its checksum is stored in a field within
the page. The checksum is recalculated when a page is read, and compared
with the stored checksum. This allows SimpleDBM to detect page corruption.</p>
<p>At present, SimpleDBM will throw an exception when corruption is
detected.</p>
</div>
</div>
</div>
<div class="section" id="buffer-manager">
<h2><a class="toc-backref" href="#id140">Buffer Manager</a><a class="headerlink" href="#buffer-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id26">
<h3><a class="toc-backref" href="#id141">Overview</a><a class="headerlink" href="#id26" title="Permalink to this headline">¶</a></h3>
<p>The Buffer Manager is a critical component of any DBMS. Its primary
job is to cache disk pages in memory. Typically, a Buffer Manager
has a fixed size Buffer Pool, implemented as an array of in-memory
disk pages. The contents of the Buffer Pool change over time, as
pages are read in, and written out. One of the principle tasks of
the Buffer Manager is to decide which page should stay in memory,
and which should not. The aim is to try to keep the most frequently
required pages in memory. The efficiency of the Buffer Manager can
be measured by its cache hit-rate, which is the ratio of pages found
in the cache, to pages accessed by the system.</p>
<p>In order to decide which pages to maintain in memory, the Buffer
Manager typically implements some form of Least Recently Used (LRU)
algorithm. In the simplest form, this is simply a linked list of all
cached pages, the head of the list representing the least recently
used page, and the tail the most recently used. This is based on the
assumption that if a page was accessed recently, then it is likely
to be accessed again soon. Since every time a page is accessed, it
is moved to the MRU end of the list, therefore over time, the most
frequently accessed pages tend to accumulate on the MRU side. Of
course, if a client reads a large number of temporary pages, then
this scheme can be upset. To avoid this, the Buffer Manager may
support hints, so that a client can provide more information to the
Buffer Manager, which can then use this information to improve the
page replacement algorithm. An example of such a hint would be to
flag temporary pages. The Buffer Manager can then use this knowledge
to decide that instead of the page going to MRU end, it goes to the
LRU end.</p>
</div>
<div class="section" id="id27">
<h3><a class="toc-backref" href="#id142">Interactions with other modules</a><a class="headerlink" href="#id27" title="Permalink to this headline">¶</a></h3>
<p>The Buffer Manager interacts with the Log Manager and the Page
Manager modules. It needs the help of the PageFactory in order to
instantiate new pages, read pages from disk, and write out dirty
pages to disk. In order to support the Write Ahead Log protocol, the
Buffer Manager must ensure that all logs related to the page in
question are flushed prior to the page being persisted to disk.</p>
<p>The Transaction Manager also interacts with the Buffer Manager.
During checkpoints, the Transaction Manager asks for a list of dirty
pages. It uses information maintained by the Buffer Manager to
determine where recovery should start. After a system restart the
Transaction Manager informs the Buffer Manager about the recovery
status of disk pages.</p>
</div>
<div class="section" id="id28">
<h3><a class="toc-backref" href="#id143">Operations</a><a class="headerlink" href="#id28" title="Permalink to this headline">¶</a></h3>
<div class="section" id="creating-a-buffer-manager-instance">
<h4><a class="toc-backref" href="#id144">Creating a Buffer Manager instance</a><a class="headerlink" href="#creating-a-buffer-manager-instance" title="Permalink to this headline">¶</a></h4>
<p>A Buffer Manager instance has a dependency on Log Manager and Page
Factory. These in turn depend upon a few other modules. The
following sample code illustrates the steps required to create a
Buffer Manager instance.</p>
<div class="highlight-python"><pre>LogFactory factory = new LogFactoryImpl();
Properties properties = new Properties();
properties.setProperty("log.ctl.1", "ctl.a");
properties.setProperty("log.ctl.2", "ctl.b");

// Create Storage Factory instance
StorageContainerFactory storageFactory =
    new FileStorageContainerFactory();
// Open Log
LogMgr log = factory.openLog(storageFactory, properties);
// Create Object Registry
ObjectFactory objectFactory = new ObjectFactoryImpl();
// Create Storage Manager instance
StorageManager storageManager = new StorageManagerImpl();
// Create Latch Factory
LatchFactory latchFactory = new LatchFactoryImpl();
// Create Page Factory
PageFactory pageFactory = new PageFactoryImpl(objectFactory,
    storageManager, latchFactory);
// Create a Buffer Manager intance with a Buffer Pool of
// 50 pages and a hash table of 101 buckets
BufMgrImpl bufmgr = new BufMgrImpl(logmgr, pageFactory, 50, 101);</pre>
</div>
<p>Note that when creating a Buffer Manager instance, you can set the
size of the Buffer Pool and also the size of the Hash table.</p>
<p>A Buffer Manager instance has a one to one relationship with a Page
Factory. Hence all pages managed by the Buffer Manager instance will
be of the same size; the page size is determined by the Page
Factory.</p>
</div>
<div class="section" id="fixing-pages-in-the-buffer-pool">
<h4><a class="toc-backref" href="#id145">Fixing Pages in the Buffer Pool</a><a class="headerlink" href="#fixing-pages-in-the-buffer-pool" title="Permalink to this headline">¶</a></h4>
<p>The Buffer Manager provides methods for fixing pages in the Buffer
Pool. There are two possibilities:</p>
<ul class="simple">
<li>Fix a new page.</li>
<li>Fix an existing page.</li>
</ul>
<p>It is the client&#8217;s responsibility to know whether the page is new or
existing. If a request is made to fix the page as new, then the
outcome may be unexpected. If the page already exists in the Buffer
Pool, it will be returned, rather than initializing a new Page.</p>
<p>When fixing a Page, the Page can be locked in one of three modes:</p>
<dl class="docutils">
<dt>Shared mode</dt>
<dd>allowing multiple clients to access the same Page concurrently
for reading.</dd>
<dt>Update mode</dt>
<dd>which allows one client to access the page in update mode,
but other clients may access the same page concurrently in
Shared mode.</dd>
<dt>Exclusive mode</dt>
<dd>in this mode only one client has access to the Page. This mode
is used when a client wishes to modify the contents of the Page.</dd>
</dl>
<p>An Update mode request can be upgraded to Exclusive mode. An
Exclusive mode request may be downgraded to an Update mode request.</p>
<p>Following code sample shows how page is fixed:</p>
<div class="highlight-python"><pre>// Fix page as New (the second parameter). The page type is mypage.
// This page type should have been registered with the Object Registry
// prior to this call. The page will be latched in Exclusive mode.
// The last parameter is a hint for the LRU replacement algorithm.
BufferAccessBlock bab = bufmgr.fixExclusive(new PageId(1, 0),
  true, "mypage", 0);</pre>
</div>
<p>As shown above, when a page is fixed, the Buffer Manager returns a
BufferAccessBlock which contains a reference to the desired page.
The Page can be accessed as follows:</p>
<div class="highlight-python"><pre>MyPage page = (MyPage) bab.getPage();</pre>
</div>
</div>
<div class="section" id="modifying-page-contents">
<h4><a class="toc-backref" href="#id146">Modifying page contents</a><a class="headerlink" href="#modifying-page-contents" title="Permalink to this headline">¶</a></h4>
<p>Note that in order to modify a Page&#8217;s content, the Page must be
fixed in Exclusive mode.</p>
<p>Also, the Write Ahead Log protocol must be obeyed. This requires the
modification to proceed as follows:</p>
<ol class="arabic simple">
<li>Fix the page in exclusive mode.</li>
<li>Generate a log record containing redo/undo information for
the modification about to be made.</li>
<li>Modify the page contents.</li>
<li>Set the Page LSN of the page and mark the page as dirty.</li>
<li>Unfix the page.</li>
</ol>
<p>Failure to follow this protocol may lead to unrecoverable changes.</p>
</div>
<div class="section" id="changing-lock-modes">
<h4><a class="toc-backref" href="#id147">Changing lock modes</a><a class="headerlink" href="#changing-lock-modes" title="Permalink to this headline">¶</a></h4>
<p>As mentioned before, pages that are locked in Update mode may be
upgraded to Exclusive mode. Pages that are locked in Exclusive mode
may be downgraded to Update mode. The BufferAccessBlock interface
provides methods that allow the lock mode to be upgraded or
downgraded.</p>
</div>
<div class="section" id="unfixing-a-page">
<h4><a class="toc-backref" href="#id148">Unfixing a Page</a><a class="headerlink" href="#unfixing-a-page" title="Permalink to this headline">¶</a></h4>
<p>It is very important to unfix a Page after the client is done with
it. Failure to do so may cause the Buffer Pool to become full and
the system will potentially come to a halt if further pages cannot
be fixed. A fixed page cannot be removed from the Buffer Pool.</p>
<p>It is also advisable to keep pages fixed for a short duration only.
If necessary the same page can be fixed again.</p>
</div>
</div>
</div>
<div class="section" id="transaction-manager">
<h2><a class="toc-backref" href="#id149">Transaction Manager</a><a class="headerlink" href="#transaction-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id29">
<h3><a class="toc-backref" href="#id150">Introduction</a><a class="headerlink" href="#id29" title="Permalink to this headline">¶</a></h3>
<p>The Transaction Manager is responsible for managing transactions. It
provides interfaces for starting new transactions, and for
committing or aborting transactions. The <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> implementation
also supports Savepoints. While the view seen by the user is simple,
the Transaction Manager is a complex module and has an elaborate
interface. This chapter will attempt to unravel the TM interface and
with the help of examples, demonstrate how this interface works and
how other modules can use this interface to participate in
Transactions.</p>
</div>
<div class="section" id="overiew">
<h3><a class="toc-backref" href="#id151">Overiew</a><a class="headerlink" href="#overiew" title="Permalink to this headline">¶</a></h3>
<p><a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>&#8216;s transaction manager is modelled after <a class="reference internal" href="#aries">[ARIES]</a>. It makes
following assumptions about the rest of the system:</p>
<ul class="simple">
<li>The system uses the Write Ahead Log protocol when making changes
to database containers.</li>
<li>The unit of change is a disk page. This means that logging is
on a per page basis.</li>
<li>The disk page contains a PageLSN field that can be used to track
the last log record that made changes to the page.</li>
<li>During checkpoints the Transaction Manager does not flush all
pages, instead it writes the Buffer Manager&#8217;s &#8220;table of contents&#8221;
to the Log. The table of contents is the list of dirty pages in
the Buffer Pool, along with their Recovery LSNs. The Recovery
LSN is the LSN of the oldest log record that could potentially
have have a change to the page. For a discussion of the Recovery
LSN please refer to Mohan&#8217;s paper on ARIES and also to section
13.4.4.1 of <a class="reference internal" href="#jgray">[JGRAY]</a>. <a class="reference internal" href="#jgray">[JGRAY]</a> refers to Recovery LSNs as <tt class="docutils literal"><span class="pre">forminlsn</span></tt>.</li>
<li>At the end of system restart, the Transaction Manager informs
the Buffer Manager the RecoveryLSN status of all dirty pages;
the Buffer Manager must therefore provide an interface for
updating the Recovery LSN of such pages.</li>
<li>The Log Manager provides a mechanism for reliably recording
the Checkpoint LSN. Also, the Log Manager supports accessing
Log Records sequentially from a starting point, as well as
randomly using the LSN.</li>
<li>The Lock Manager provides an interface for acquiring and
release locks. The release mode must support a mechanism for
forcing the release of a lock.</li>
</ul>
</div>
<div class="section" id="what-is-aries">
<h3><a class="toc-backref" href="#id152">What is ARIES?</a><a class="headerlink" href="#what-is-aries" title="Permalink to this headline">¶</a></h3>
<p>ARIES is a Transaction Logging and Recovery algorithm developed at
IBM and published by IBM researcher C. Mohan.</p>
<p>For a full description of ARIES, please see <tt class="docutils literal"><span class="pre">Mohan,</span> <span class="pre">C.,</span>
<span class="pre">Haderle,</span> <span class="pre">D.,</span> <span class="pre">Lindsay,</span> <span class="pre">B.,</span> <span class="pre">Pirahesh,</span> <span class="pre">H.,</span> <span class="pre">Schwarz,</span> <span class="pre">P.</span> <span class="pre">ARIES:</span> <span class="pre">A</span>
<span class="pre">Transaction</span> <span class="pre">Recovery</span> <span class="pre">Method</span> <span class="pre">Supporting</span> <span class="pre">Fine-Granularity</span> <span class="pre">Locking</span> <span class="pre">and</span>
<span class="pre">Partial</span> <span class="pre">Rollbacks</span> <span class="pre">Using</span> <span class="pre">Write-Ahead</span> <span class="pre">Logging,</span> <span class="pre">ACM</span> <span class="pre">Transactions</span> <span class="pre">on</span>
<span class="pre">Database</span> <span class="pre">Systems,</span> <span class="pre">Vol.</span> <span class="pre">17,</span> <span class="pre">No.</span> <span class="pre">1,</span> <span class="pre">March</span> <span class="pre">1992,</span> <span class="pre">pp94-162.</span></tt></p>
<p>A brief overview of ARIES is given below.</p>
</div>
<div class="section" id="aries-an-overview">
<h3><a class="toc-backref" href="#id153">ARIES - An Overview</a><a class="headerlink" href="#aries-an-overview" title="Permalink to this headline">¶</a></h3>
<p>Following is a brief description of the main principles behind
ARIES.</p>
<p>Firstly, in ARIES, changes always take the system forward. That is
to say, even transaction rollbacks are treated as if they are
updates to the system. This is counter-inituitive to what the user
thinks, because when a user asks for a transaction to be rolled
back, they assume that the system is going back to a previous state
of affairs. However, from the perspective of ARIES, there is no such
thing as going back. For example, if a transaction changes A to B
and then rolls back, ARIES treats the rollback as simply an update
that changes B to A. The forward change from A to B (redo) and the
reversal of B to A (undo) are both recorded as updates to the
system. Changes during normal operations are recorded as Redo-Undo
log records. As the name implies, these log records can be &#8216;redone&#8217;
in case of a system crash, or &#8216;undone&#8217; in case a rollback is
required. Changes made during rollbacks, however, are recorded as
Redo-only log records. These log records are called Compensation Log
Records (CLRs). The reason these are redo only is that by definition
a rollback does not need to be undone, whereas normal updates need
to be undone if the transaction decides to rollback.</p>
<p>The second basic principle of ARIES is that during recovery, history
is repeated. This can be explained as follows.</p>
<p>When a system crashes, there would be some transactions that have
completed (committed or aborted), and others that are still active.
The WAL protocol ensures that changes made by completed transactions
have been recorded in the Log. Changes made by incomplete
transactions may also be present in the Log, because Log Records are
created in the same order as the changes are made by the system.</p>
<p>During recovery, ARIES initially replays the Log to the bring the
system back to a state close to that when the crash occurred. This
means that ARIES replays the effects of not only those transactions
that committed or aborted, but also those that were active at the
time of the crash. Having brought the system to this state, ARIES
then identifies transactions that were incomplete, and rolls them
back. The basic idea is to repeat the entire history upto the point
of crash, and then undo failed transactions.</p>
<p>This approach has the advantage that during the redo phase, changes
can be replayed at a fairly low level, for example, the level of a
disk page. ARIES calls this page oriented redo. This feature is
significant because it means that until the redo phase is over, the
system does not need to know about higher level data structures such
as Indexes. Only during the undo phase, when incomplete transactions
are being rolled back, does the system need to know about high level
data structures.</p>
</div>
<div class="section" id="features-of-aries">
<h3><a class="toc-backref" href="#id154">Features of ARIES</a><a class="headerlink" href="#features-of-aries" title="Permalink to this headline">¶</a></h3>
<p>ARIES includes a number of optimisations to reduce the amount of
work required during normal operations and recovery.</p>
<p>One optimisation is to avoid application of log records
unnecessarily. The LSN of the most recently generated log record is
stored in each disk page. This is known as the PageLsn. The PageLsn
allows ARIES to determine during the redo phase, whether the changes
represented by a log record have been applied to the page or not.</p>
<p>ARIES chains log records for transactions in such a way that those
records that are no longer necessary, are skipped during recovery.
For example, if a transaction changed A to B, and then rolled back,
generating a log record for changing B to A, then during recovery,
ARIES would automatically skip the log record that represents the
change from A to B. This is made possible by maintaining a UndoLsn
pointer in every Log Record. The UndoLsn normally points to the
previous log record generated by the transaction. However, in log
records generated during Rollback (known as Compensation Log
Records), the UndoLsn is made to point to the Log record preceding
the one that is being undone. To take an example, let us assume that
a transaction generated log record 1, containing change from A to B,
then log record 2 containing change from B to C. At this point the
transaction decides to rollback the change from B to C. It therefore
generates a new log record 3, containing a change from C to B. The
UndoLsn of this log record is made to point at log record 1, instead
of log record 2. When following the UndoLsn chain, ARIES would skip
log record 2.</p>
<p>ARIES also supports efficient checkpoints. During a checkpoint, it
is not necessary to flush all database pages to disk. Instead ARIES
records a list of dirty buffer pages along with their
RecoveryLsn(s). The RecoveryLsn of a page is the LSN of the earliest
log record that represents a change to the page since it was read
from disk. By using this list, ARIES is able to determine during
recovery, where to start replaying the Log.</p>
<p>ARIES supports nested top-level action concept whereby part of a
transaction can be committed even if the transaction aborts. This is
useful for situations where a structural change should not be undone
even if the transaction aborts. Nested top level actions are
implemented using Dummy Compensation Log Records - and make use of
the ability to skip logs records using the UndoLsn pointer as
described previously.</p>
</div>
<div class="section" id="key-differences-from-aries">
<h3><a class="toc-backref" href="#id155">Key differences from ARIES</a><a class="headerlink" href="#key-differences-from-aries" title="Permalink to this headline">¶</a></h3>
<p>The implementation of the Transaction Manager in SimpleDBM is as faithful
to ARIES as possible, with a few differences.</p>
<ul class="simple">
<li>SimpleDBM supports multi-page redo operations where a single log record
affects multiple pages.</li>
<li>SimpleDBM records in the checkpoint records the list of open containers
so that it can ensure that these containers are re-opened at startup.</li>
<li>The transaction manager supports post commit actions for handling of
special cases such as deleting a container.</li>
<li>The transaction manager supports non-page specific log records for operations
such as opening/deleting containers.</li>
</ul>
</div>
<div class="section" id="transactions-and-locks">
<h3><a class="toc-backref" href="#id156">Transactions and Locks</a><a class="headerlink" href="#transactions-and-locks" title="Permalink to this headline">¶</a></h3>
<p>There is close coordination between the Transaction Manager and the
Lock Manager. A Transaction needs to keep track of all locks
acquired on its behalf so that it can release them when the
Transaction completes. This is why the Transaction interface in
<a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> provides methods for acquiring locks. If the Lock Manager
is invoked directly by the client then the TM has no way of knowing
which locks to release when the Transaction terminates.</p>
<p>While locks can be acquired by a client any time after a Transaction
starts, locks are released only on one of the following three
occasions:</p>
<ul class="simple">
<li>If the CURSOR STABILITY Isolation Mode is being used, then a
SHARED or UPDATE lock can be released once the cursor moves
to the next record. If REPEATABLE READ Isolation Mode is
used, then the UPDATE lock can be downgraded to SHARED lock
when the cursor moves. Note that the Transaction Manager does
not decide when to release or downgrade a lock; it is the
responsibility of the client to decide that. However, the
Transaction must update its record of the locks when this
happens. Therefore, lock release or downgrade requests
must be handled via the Transaction interface and not
directly between the client and the Lock Manager.</li>
<li>When a Transaction is rolled back to a Savepoint, any
locks acquired after the Savepoint are released. Note that
if a lock was acquired before the Savepoint, and upgraded
after the Savepoint, it will not be downgraded or released.
The Transaction interface manages the release of such locks.</li>
<li>Finally, when the Transaction completes, all locks held by
the transaction are released.</li>
</ul>
<p>Following sample code shows how a client interacts with the
Transaction.</p>
<div class="highlight-python"><pre>// Start new Transaction
Transaction trx = trxmgr.begin();

// Acquire a shared lock
trx.acquireLock(new ObjectLock(1,15), LockMode.SHARED,
   LockDuration.MANUAL_DURATION);

// Upgrade the shared lock
trx.acquireLock(new ObjectLock(1,15), LockMode.UPDATE,
LockDuration.MANUAL_DURATION);

// Downgrade the update lock
trx.downgradeLock(new ObjectLock(1, 15),
   LockMode.SHARED);

// commit the transaction, releasing all locks
trx.commit();</pre>
</div>
</div>
<div class="section" id="transactions-and-modules">
<h3><a class="toc-backref" href="#id157">Transactions and Modules</a><a class="headerlink" href="#transactions-and-modules" title="Permalink to this headline">¶</a></h3>
<p>The Transaction Manager provides a framework for managing
transactions. It provides interfaces to:</p>
<ol class="arabic simple">
<li>Start and end transactions</li>
<li>Acquire locks on behalf of transactions</li>
<li>Create log records on behalf of transactions.</li>
</ol>
<p>The Transaction Manager itself does not initiate changes to database
pages, though it may coordinate the redo or undo of such changes &#8211;
changes are always initiated by clients. A client in this context is
some module within the system that wishes to make changes to the
database disk pages as part of a Transaction.</p>
<p>The Transaction Manager does not know in advance what clients it may
have to interact with. However, it needs to be able to call upon the
clients to redo or undo the effects of log records when required.
This is enabled in two ways:</p>
<ol class="arabic simple">
<li>Firstly, all clients must implement the TransactionalModule
interface. This interface defines the operations that the
Transaction Manager may call upon the client to perform.</li>
<li>Secondly, all modules must <em>register</em> themselves to the
Transaction Manager using unique Module IDs. This way, the
Transaction Manager knows how to obtain access to a module,
and ask it to perform an action.</li>
<li>Finally, all log records generated by a Module need to be
tagged with the Module&#8217;s Unique ID. If this is not done,
the Transaction Manager would not know which module is
responsible for handling a particular log record.</li>
</ol>
</div>
<div class="section" id="transactions-and-log-records">
<h3><a class="toc-backref" href="#id158">Transactions and Log records</a><a class="headerlink" href="#transactions-and-log-records" title="Permalink to this headline">¶</a></h3>
<p>The Transaction Manager works very closely with the Log Manager to
ensure the ACID properties of transactions. We saw in the chapter on
Log Manager that it does not care about the contents of Log Records.
The Transaction Manager, however, does care, and defines a hierarchy
of different Log record types that should be used by clients. This
is explained below.</p>
</div>
<div class="section" id="the-loggable-hierarchy">
<h3><a class="toc-backref" href="#id159">The Loggable hierarchy</a><a class="headerlink" href="#the-loggable-hierarchy" title="Permalink to this headline">¶</a></h3>
<p>Loggable is parent interface for all Log Records. The Transaction
Manager will only accept Log records that implement this interface.
This can be seen from the signature of the logInsert() method
provided by the Transaction interface.</p>
<p>The Loggable hierarchy defines the various types of log records that
clients can generate. These are further discussed below.</p>
<div class="section" id="loggable-hierarchy">
<h4><a class="toc-backref" href="#id160">Loggable Hierarchy</a><a class="headerlink" href="#loggable-hierarchy" title="Permalink to this headline">¶</a></h4>
<p>The main branches of the Loggable hierarchy are shown below. Note
that some of the hierarchy is not visible to outside clients (marked
as internal).</p>
<table border="1" class="docutils">
<caption>Loggable Hierarchy</caption>
<colgroup>
<col width="42%" />
<col width="58%" />
</colgroup>
<thead valign="bottom">
<tr><th class="head">Interface</th>
<th class="head">Description</th>
</tr>
</thead>
<tbody valign="top">
<tr><td>Redoable</td>
<td>All log operations that affect database
pages must implement this interface or one
of its sub-interfaces. The Transaction
Manager expects a valid PageId (s) to be
returned by a Redoable log record. Note
that Compensation and Undoable log records
are sub-interfaces of Redoable.</td>
</tr>
<tr><td>NonTransactionRelatedOperation</td>
<td>These represent changes that are not
related to specific pages. Since the ARIES
algorithm uses page LSNs to track updates
caused by log records, changes made by
this type of log record are not tracked
they are repeated unconditionally at
system start. At present, this type of log
operation is used to handle opening of
containers.</td>
</tr>
<tr><td>PostCommitAction</td>
<td>Although PostCommitAction is a
subinterface of
NonTransactionRelatedOperation at present,
this may change in
future. PostCommitActions are used to
schedule actions that must be performed
after a successful commit. An example of
such an action is the dropping of a
container. To avoid logging the full
contents of the container, the actual
delete of the container must be deferred
until it is certain that the Transaction
is committing.  Note that unlike other
NonTransactionRelatedOperations, the
Transaction Manager does track the status
of PostCommitActions and will execute them
at restart if they have not been executed.</td>
</tr>
<tr><td>ContainerDeleteOperation</td>
<td>The Transaction Manager needs to be aware
when containers are deleted, both when a
container is dropped or when the creation
of a container is aborted. In both cases,
the TM uses this marker interface to
identify the delete operation and
coordinates with the Buffer Manager to
clear the cached pages related to the
deleted container.</td>
</tr>
<tr><td>ContainerOpenOperation</td>
<td>The Transaction Manager needs to be aware
when containers are opened between
checkpoints so that it can include these
in the next checkpoint.
The TM uses this marker interface to
identify the open operation.</td>
</tr>
</tbody>
</table>
</div>
<div class="section" id="transaction-manager-internal-log-records">
<h4><a class="toc-backref" href="#id161">Transaction Manager Internal Log Records</a><a class="headerlink" href="#transaction-manager-internal-log-records" title="Permalink to this headline">¶</a></h4>
<p>The Transaction Manager uses internal log records to track
Transaction completion, and also Checkpoints. These log record types
are not available outside the implementation of the TM.</p>
</div>
<div class="section" id="redoable">
<h4><a class="toc-backref" href="#id162">Redoable</a><a class="headerlink" href="#redoable" title="Permalink to this headline">¶</a></h4>
<p>Generally speaking, most log records are implementations of Redoable
interface or one of its sub-interfaces. A Redoable log record is
related to one or more database pages, and can be re-done at System
restart. In some cases, the effects of a log record should not be
undone; such records are called Redo-only log records and can be
created in a number of ways:</p>
<ul class="simple">
<li>Implement the Redoable interface but not its Undoable sub-interface.</li>
<li>Implement the Compensation interface. This is a special case,
which is discussed later.</li>
</ul>
<p>An example of a Redo-only log record is the Page Format operation.
Newly created pages need to be formatted, but once this is done, it
is unnecessary to undo the formatting.</p>
<p>Given below is an example implementation of a Page Format log
record:</p>
<div class="highlight-python"><pre>public static class FormatRawPage extends BaseLoggable
  implements Redoable, PageFormatOperation {

  ByteString dataPageType;

  public void init() {
  }

  public final String getDataPageType() {
      return dataPageType.toString();
  }

  public final void setDataPageType(String dataPageType) {
      this.dataPageType = new ByteString(dataPageType);
  }

  public int getStoredLength() {
      return super.getStoredLength() +
          dataPageType.getStoredLength();
  }

  public void retrieve(ByteBuffer bb) {
      super.retrieve(bb);
      dataPageType = new ByteString();
      dataPageType.retrieve(bb);
  }

  public void store(ByteBuffer bb) {
      super.store(bb);
      dataPageType.store(bb);
  }
}</pre>
</div>
<p>As astute reader will notice that the Page Format operation extends
the BaseLoggable class and implements both Redoable and
PageFormatOperation interfaces. The BaseLoggable class and the
PageFormatOperation interface are described further below.</p>
</div>
<div class="section" id="baseloggable-abstract-class">
<h4><a class="toc-backref" href="#id163">BaseLoggable abstract class</a><a class="headerlink" href="#baseloggable-abstract-class" title="Permalink to this headline">¶</a></h4>
<p>The Transaction Manager provides the BaseLoggable abstract class
which implements the Loggable interface. Rather than attempting to
implement the Loggable interface from scratch, it is highly
recommended that clients sub-class the BaseLoggable class and extend
it to add functionality. The reason for making Loggable an interface
and not an abstract class like BaseLoggable is that it allows the
client to implement its own class hierarchy independently from the
Loggable hierarchy.</p>
</div>
<div class="section" id="pageformatoperation">
<h4><a class="toc-backref" href="#id164">PageFormatOperation</a><a class="headerlink" href="#pageformatoperation" title="Permalink to this headline">¶</a></h4>
<p>Operations that format new pages are particularly important because
the Transaction Manager must invoke the Buffer Manager FIX AS NEW
interface to fix pages affected by them. If the normal fix interface
is called, an exception will be thrown because the page may not
exist on disk or may be garbage. To allow the Transaction Manager to
spot page format operations, all log records that perform such
actions should implement the PageFormatOperation interface. This is
a marker interface only.</p>
<p>Usually, PageFormatOperations are redo-only.</p>
<p>In <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>, the page format operations are handled when a
container is created or expanded.</p>
</div>
<div class="section" id="multipageredo">
<h4><a class="toc-backref" href="#id165">MultiPageRedo</a><a class="headerlink" href="#multipageredo" title="Permalink to this headline">¶</a></h4>
<p>Normally a Redoable log record represents changes to a single page.
Sometimes, however, it may be necessary for a single log record to
contain changes made to multiple pages. In such cases, the Log
record should implement the MultiPageRedo interface.</p>
<p>Note that clients need to follow the following procedure when
creating MultiPageRedo log records.</p>
<ol class="arabic simple">
<li>Fix all the affected pages.</li>
<li>Generate the MultiPageRedo log record.</li>
<li>Apply changes to the affected pages.</li>
<li>Set the pageLsn of all affected pages to the LSN of the
log record.</li>
<li>Unfix all affected pages.</li>
</ol>
</div>
<div class="section" id="undoable">
<h4><a class="toc-backref" href="#id166">Undoable</a><a class="headerlink" href="#undoable" title="Permalink to this headline">¶</a></h4>
<p>Logs records that need to be undoable should implement the Undoable
interface. The Undoable interface extends the Redoable interface,
thus, undoable log records are by definition redoable as well.</p>
<p>An Undoable log record should contain data that can be used to
<em>redo</em> the changes, as well as to <em>undo</em> the changes. Typically,
this means that both old and new values must be stored. For example,
if the log is to represent changing a field value from A to B, then
its old value will be A, and new value will be B.</p>
<p>At system restart, Undoable records are redone. This means that the
redo portion of such log records are applied. In the example given
above, this would cause the field value to be set to B.</p>
<p>When the Transaction Manager needs to undo the changes represented
by an Undoable record, it will ask the client to perform one of
following depending upon the type of Undoable record:</p>
<ul class="simple">
<li>If the Undoable record is an instance of SinglePageLogicalUndo,
then the Transaction Manager assumes that the undo operation
must be performed against some page other than the one
originally affected. However, the undo is known to affect only
one page. In this situation the Transaction Manager requests
the client to identify the page to which undo should be applied,
and then coordinates the generation of undo as normal.</li>
<li>If the Undoable record is an instance of LogicalUndo, then the
Transaction Manager assumes that the undo operation is not an
exact inverse of the redo operation and may require updates
to one or more pages. It also assumes that the client may
generate additional log records. For such log records, the
client is given full control over how the undo is to be
performed.</li>
<li>If neither of above are true, then the Transaction Manager
assumes that the Undo operation is <em>physical</em>, i.e., it is to
be applied to the same page that was affected by the original
change. In this case, it requests the client to generate the
undo information (Compensation) which is then applied as a
redo operation.</li>
</ul>
<p>Following sections describe above in reverse order.</p>
</div>
<div class="section" id="physical-undos">
<h4><a class="toc-backref" href="#id167">Physical Undos</a><a class="headerlink" href="#physical-undos" title="Permalink to this headline">¶</a></h4>
<p>The simplest case is that of a Physical Undo, where the undo
operation affects the same page that was originally modified during
forward change (i.e., redo). In this case, the Transaction Manager
asks the client to generate a Compensation record for redoing the
undo operation. This is then applied to the affected page using the
redo interface provided by the client. Following code shows how the
Transaction Manager interacts with the client:</p>
<div class="highlight-python"><pre>Compensation clr = module.generateCompensation(undoable);
....
module.redo(page, clr);</pre>
</div>
<p>Thus, for this type of log record, the client must implement the
generateCompensation(Undoable) and redo(Page, Redoable) operations.</p>
</div>
<div class="section" id="singlepagelogicalundos">
<h4><a class="toc-backref" href="#id168">SinglePageLogicalUndos</a><a class="headerlink" href="#singlepagelogicalundos" title="Permalink to this headline">¶</a></h4>
<p>SinglePageLogicalUndos are slightly more complex than Physical
undos. The undo operation is guaranteed to affect one page only, but
it may not be the page originally affected. To handle this scenario,
the Transaction Manager first asks the client to identify the page
where the undo is to be applied. Once this has been done, the
process is identical to that of Physical undos. Following code
extract shows how the TM interacts with the client:</p>
<div class="highlight-python"><pre>BufferAccessBlock bab = module.findAndFixPageForUndo(undoable);
...
Compensation clr = module.generateCompensation(undoable);
...
module.redo(bab.getPage(), clr);
...
bab.unfix();</pre>
</div>
<p>What above shows is that the client is responsible for identifying
and fixing the appropriate page &#8211; the page is unfixed by
Transaction Manager once the change has been applied.</p>
</div>
<div class="section" id="logicalundos">
<h4><a class="toc-backref" href="#id169">LogicalUndos</a><a class="headerlink" href="#logicalundos" title="Permalink to this headline">¶</a></h4>
<p>From the client&#8217;s perspective the most complex type of undo is where
the undo operation may impact several pages, and may result in
additional log records being generated.</p>
<p>For such records, the Transaction Manager simply invokes the
client&#8217;s undo interface as follows:</p>
<div class="highlight-python"><div class="highlight"><pre><span class="n">module</span><span class="o">.</span><span class="n">undo</span><span class="p">(</span><span class="n">trx</span><span class="p">,</span> <span class="n">undoable</span><span class="p">)</span>
</pre></div>
</div>
<p>It is the client&#8217;s responsibility to generate appropriate log
records and make changes to database pages.</p>
</div>
<div class="section" id="comments-about-implementing-undo-operations">
<h4><a class="toc-backref" href="#id170">Comments about implementing undo operations</a><a class="headerlink" href="#comments-about-implementing-undo-operations" title="Permalink to this headline">¶</a></h4>
<p>From the discussion above, it should be clear that Physical undos
are the easiest to implement. They are also the most efficient.
However, in some cases, notably in Index operations, physical undos
may not be optimum. This is because in a BTree Index, a key can move from
one page to another as a result of page splits or page merges.</p>
<p>In some BTree implementations, such as in Apache Derby, the undo
operations are limited to a single page. This is achieved through
the use of <em>logical key deletes</em>.</p>
<p>Where keys are physically deleted, undo of key deletes may cause
page splits. Such undo operations may impact more than one page. The
<a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> BTree implementation is an example of this type of
operation.</p>
</div>
<div class="section" id="compensation-records">
<h4><a class="toc-backref" href="#id171">Compensation records</a><a class="headerlink" href="#compensation-records" title="Permalink to this headline">¶</a></h4>
<p>Undo operations are represented using Compensation log records. The
benefits of using Compensation log records are explained in detail
by Mohan in the ARIES paper. As Mohan explains in his paper, a
Compensation record is redo-only &#8211; it is never undone. A unique
property of ARIES algorithm is that Compensation log records are
linked back to the predecessor of the log record that is being
undone. This backward chaining allows ARIES to skip processing of
undo operations that are already applied.</p>
<p>While Compensation log records are mostly used to represent undo
operations, sometimes, they can be effectively used to represent
redo operations as well. The system can make use of the backward
chaining to allow certain log records to be skipped in the event of
an undo. This feature is the basis for the Nested Top Action concept
in ARIES. It is also exploited by the <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> BTree implementation
to reduce the amount of logging required for structure modification
operations. For further details, please refer to the paper entitled
&#8211; <tt class="docutils literal"><span class="pre">Space</span> <span class="pre">Management</span> <span class="pre">issues</span> <span class="pre">in</span> <span class="pre">B-Link</span> <span class="pre">trees</span></tt>.</p>
</div>
<div class="section" id="nontransactionrelatedoperations">
<h4><a class="toc-backref" href="#id172">NonTransactionRelatedOperations</a><a class="headerlink" href="#nontransactionrelatedoperations" title="Permalink to this headline">¶</a></h4>
<p>A NonTransactionRelatedOperation is one that should be redone
without reference to a database page. Note that such operations are
discarded after a Checkpoint, i.e, only those records will be redone
that are encountered after the last Checkpoint. Is is therefore
important to ensure that the effect of these log records are also
saved in Checkpoint operations.</p>
<p>In <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>, the only use of this operation at present is to log
opening of containers. After a container is created, a
NonTransactionRelatedOperation is logged to ensure that the
container will be reopened at system restart. A Checkpoint operation
in <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> includes a list of all open containers, hence, any past
open container log records become redundant after the Checkpoint.</p>
</div>
<div class="section" id="postcommitactions">
<h4><a class="toc-backref" href="#id173">PostCommitActions</a><a class="headerlink" href="#postcommitactions" title="Permalink to this headline">¶</a></h4>
<p>PostCommitActions are used to defer certain actions until it is
known for sure that the Transaction is definitely committing. In
<a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>, dropping a container is handled this way. When a request
is made by a client to drop a container, a PostCommitAction is
scheduled to occur once the transaction commits.</p>
<p>The Transaction Manager tracks the status of PostCommitActions and
ensures that once a transaction has committed, its PostCommitActions
are executed even if there is a system crash. This is achieved by
logging such actions as part of the transaction&#8217;s Prepare log
record. Note that a PostCommitAction may be executed more than once
by the TransactionManager, hence it should be coded in such a way
that there is no adverse impact if the operation is repeated. For
example, if the action is to delete a container, it would be
erroneous for the PostCommitAction to complain if the container is
already deleted.</p>
</div>
<div class="section" id="containerdeleteoperations">
<h4><a class="toc-backref" href="#id174">ContainerDeleteOperations</a><a class="headerlink" href="#containerdeleteoperations" title="Permalink to this headline">¶</a></h4>
<p>Since an ARIES style Transaction Manager operates at the level of
disk pages, it is necessary to know when a container has been
deleted so that all pages related to the container can be marked
invalid. Also, the container needs to be closed to prevent further
changes to it. The Transaction Manager uses the
ContainerDeleteOperation interface as a marker interface to identify
log records that are going to cause containers to be dropped.</p>
</div>
<div class="section" id="containeropenoperations">
<h4><a class="toc-backref" href="#id175">ContainerOpenOperations</a><a class="headerlink" href="#containeropenoperations" title="Permalink to this headline">¶</a></h4>
<p>The TransactionManager maintains a list of open containers in
the checkpoint record. At restart, it needs to identify containers
created since the last checkpoint; it does this by tracking any
ContainerOpenOperation records. A container is reopened if the
ContainerOpenOperation is valid, i.e., it has not been superceded
by a later ContainerDeleteOperation.</p>
</div>
</div>
</div>
<div class="section" id="space-manager">
<h2><a class="toc-backref" href="#id176">Space Manager</a><a class="headerlink" href="#space-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id33">
<h3><a class="toc-backref" href="#id177">Introduction</a><a class="headerlink" href="#id33" title="Permalink to this headline">¶</a></h3>
<p>The Space Manager module is responsible for managing free space
information within a Storage Container. Using free space
information, the Space Manager module can find pages that meet space
requirements of clients. The Space Manager module also handles
creation of new containers and expansion/deletion of existing
containers.</p>
</div>
<div class="section" id="comparison-with-storage-manager-module">
<h3><a class="toc-backref" href="#id178">Comparison with Storage Manager module</a><a class="headerlink" href="#comparison-with-storage-manager-module" title="Permalink to this headline">¶</a></h3>
<p>We have previously encountered the Storage Manager module which
provides facilities for creating and dropping specific containers.
However, these operations are low-level, and not transactional.
Containers created by the Storage Manager module are raw, and do not
have any structure.</p>
<p>The Space Manager module implements a higher level interface. It
differs from the Storage Manager module in following ways:</p>
<ul class="simple">
<li>Its operations are transactional.</li>
<li>Containers have a predefined structure and support fixed-size
pages.</li>
<li>The Space Manager module implements special pages within the
container where information about other pages is maintained.
This information can be used to quickly locate a page with
specified amount of storage.</li>
</ul>
</div>
<div class="section" id="id34">
<h3><a class="toc-backref" href="#id179">Operations</a><a class="headerlink" href="#id34" title="Permalink to this headline">¶</a></h3>
<div class="section" id="obtaining-an-instance-of-spacemgr">
<h4><a class="toc-backref" href="#id180">Obtaining an instance of SpaceMgr</a><a class="headerlink" href="#obtaining-an-instance-of-spacemgr" title="Permalink to this headline">¶</a></h4>
<p>The default implementation of the SpaceMgr module is
org.simpledbm.rss.sm.impl.SpaceMgrImpl.
As can be seen in the example below, the SpaceMgr module depends
upon a number of other modules.</p>
<div class="highlight-python"><pre>SpaceMgr spacemgr = new SpaceMgrImpl(objectFactory, pageFactory,
  logmgr, bufmgr, storageManager, storageFactory,
  loggableFactory, trxmgr, moduleRegistry);</pre>
</div>
</div>
<div class="section" id="creating-a-container">
<h4><a class="toc-backref" href="#id181">Creating a Container</a><a class="headerlink" href="#creating-a-container" title="Permalink to this headline">¶</a></h4>
<p>Following sample code demonstrates how to create a Container. Note
that for correct operation, the container ID allocated to the new
container should be locked exclusively prior to creating the
container. This will prevent other transactions from manipulating
the same container.</p>
<div class="highlight-python"><pre>SpaceMgr spacemgr = new SpaceMgrImpl(...);
Transaction trx = trxmgr.begin();
boolean okay = false;
try {
  // Create a new Container named testctr.dat and assign it a container
  // ID of 1. This container will use RawPages as its data page.

  int containerId = 1;
  int spaceBits = 1;
  int extentSize = 64;
  spacemgr.createContainer(trx, "testctr.dat", containerId,
     spaceBits, extentSize, pageFactory.getRawPageType());

  okay = true;
}
finally {
  if (okay) {
     trx.commit();
  }
  else {
     trx.abort();
  }
}</pre>
</div>
<p>Note that the container create operation is transactional.</p>
</div>
<div class="section" id="extending-a-container">
<h4><a class="toc-backref" href="#id182">Extending a Container</a><a class="headerlink" href="#extending-a-container" title="Permalink to this headline">¶</a></h4>
<p>When a container is initially created, it is allocated an extent of
specified size. The extent is the minimum allocation unit for a
container; a container is always expanded in extents.</p>
<div class="highlight-python"><pre>Transaction trx = trxmgr.begin();
spacemgr.extendContainer(trx, 1);
trx.commit();</pre>
</div>
</div>
<div class="section" id="deleting-a-container">
<h4><a class="toc-backref" href="#id183">Deleting a container</a><a class="headerlink" href="#deleting-a-container" title="Permalink to this headline">¶</a></h4>
<p>Note that prior to deleting a container, you must acquire an
Exclusive lock on the container ID. This will prevent other transactions
from accessing the same container.</p>
<p>Deleting a container is as simple an operation as extending it:</p>
<div class="highlight-python"><pre>Transaction trx = trxmgr.begin();
spacemgr.dropContainer(trx, 1);
trx.commit();</pre>
</div>
<p>An important point to note about the container delete operation
is that the physical removal of the container is deferred until
the transaction commits. This is done to allow the delete operation
to be rolled back in case the transaction aborts.</p>
<p>A limitation in the current implementation is that the container
is not physically removed. This will be fixed in a future revision
of the module.</p>
</div>
<div class="section" id="searching-for-free-space">
<h4><a class="toc-backref" href="#id184">Searching for free space</a><a class="headerlink" href="#searching-for-free-space" title="Permalink to this headline">¶</a></h4>
<p>At the time of creating a container, you can specify the number
of bits that should be used to track space information for each
individual page. At present, you can either use a single
bit or two bits. If one bit is used, the possible values are
0 and 1, if two bits are used, then the possible values are 0,
1,2 and 3. The SpaceMgr module initializes the space bits with a
value of 0, hence this value always means unused or unallocated
space. The interpretation of other values is upto the client;
SpaceMgr merely provides the mechanism to maintain
this data.</p>
<p>As an example, in the BTree module, containers are created with
a single bit for each page. The value 0 is used to identify
unallocated pages, 1 is used for allocated pages.</p>
<p>In order to search for free space, you first need to obtain
a SpaceCursor. The SpaceCursor mechanism allows you to perform
following actions:</p>
<ul class="simple">
<li>Search for page with specified space usage, and fix
associated space map page exclusively.</li>
<li>Update the space map information for a page, and log this
operation.</li>
<li>Fix a specific space map page.</li>
<li>Unfix the currently fixed space map page.</li>
</ul>
<p>When you search for free space, you need to provide an implementation
of <tt class="docutils literal"><span class="pre">SpaceChecker</span></tt>; this will be invoked by SpaceMgr module to
check whether a page meets the space requirements of the client.</p>
<p>Here is an example of a search that attempts to locate pages that
are unallocated:</p>
<div class="highlight-python"><pre>int pageNumber = spaceCursor.
     findAndFixSpaceMapPageExclusively(new SpaceChecker() {
  public boolean hasSpace(int value) {
     return value == 0;
  }
});</pre>
</div>
<p>If the SpaceCursor cannot locate a suitable page, it returns -1. Otherwise it
returns the page that satisfied the space request.</p>
<p>An important point to note is that just because space map information
indicates that the page has free space, does not always mean that the page
will be able to satisfy the request. Some modules, such as the TupleMgr
module, may mark pages as free even though they are still occupied.
Please refer to the TupleMgr documentation to understand why this is
so. In general, it is upto the client module to ensure that the space
map information is accurate and up-to-date.</p>
<p>Usually, if the space map search returns -1, the container needs to be
extended and then the search retried.</p>
</div>
<div class="section" id="updating-space-information">
<h4><a class="toc-backref" href="#id185">Updating space information</a><a class="headerlink" href="#updating-space-information" title="Permalink to this headline">¶</a></h4>
<p>A successful search will result in the space map page being exclusively
latched. Hence, after the search, the client must unfix the page. Failure
to do so will cause pages to remain fixed and exhaust the Buffer Pool.
The SpaceCursor interface provides an interface for unfixing the
currently fixed space map page.</p>
<div class="highlight-python"><pre>Transaction trx = trxmgr.begin();
spaceCursor.updateAndLogRedoOnly(trx, pageNumber, 1);
spaceCursor.unfixCurrentSpaceMapPage();
trx.commit();</pre>
</div>
<p>Above example also shows how to update the space map page information
and also log it to the Write Ahead Log.</p>
<p>There will be times when the client wishes to update the space
information for a specific page. In this situation it is the client&#8217;s
responsibility to know which space map page contains the associated
data.</p>
<p>The SpaceCursor interface supports accessing a specific space
map page, provided it is known which page is desired:</p>
<div class="highlight-python"><pre>Transaction trx = trxmgr.begin();
SpaceCursor spcursor = spaceMgr.getSpaceCursor(containerId);
spcursor.fixSpaceMapPageExclusively(spaceMapPageNumber,
  pageNumber);
try {
  pcursor.updateAndLogRedoOnly(trx, pageNumber, spacebits);
} finally {
  spcursor.unfixCurrentSpaceMapPage();
}
trx.commit();</pre>
</div>
</div>
</div>
</div>
<div class="section" id="slotted-page-manager">
<h2><a class="toc-backref" href="#id186">Slotted Page Manager</a><a class="headerlink" href="#slotted-page-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id35">
<h3><a class="toc-backref" href="#id187">Introduction</a><a class="headerlink" href="#id35" title="Permalink to this headline">¶</a></h3>
<p><a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>, like most other databases, stores records in fixed size
pages. The Slotted Page Manager module provides an enhancement to
the Raw Page by allowing records to be inserted, updated and deleted
within the page. By providing a common infrastructure, client
modules such as the B-Tree Manager or the Tuple Manager can
concentrate on higher level functions.</p>
</div>
<div class="section" id="structure-of-slotted-page">
<h3><a class="toc-backref" href="#id188">Structure of Slotted Page</a><a class="headerlink" href="#structure-of-slotted-page" title="Permalink to this headline">¶</a></h3>
<p>From the client perspective, the structure of the Slotted Page is
not relevant in its details. What matters is the interface. A key
requirement is to be able to access records quickly within the page,
using a numeric identifier called Slot Number.</p>
<p>Each record in the page is assigned a Slot Number. Slot Numbers
start from 0, ie, the first record in the page can be accessed via
Slot Number 0.</p>
<p>In addition to storing the record data, each Slot is also capable of
storing a set of flags in a Short integer. The interpretation of
these flags is up to the client module.</p>
<p>Records may be inserted at a specific Slot position, updated and
deleted. Deleted records leave the Slot unoccupied, but do not shift
records. A purge interface is available which completely removes the
record specified and also shifts to the left all records to the right of
the purged record.</p>
</div>
<div class="section" id="obtaining-instances-of-slotted-page">
<h3><a class="toc-backref" href="#id189">Obtaining instances of Slotted Page</a><a class="headerlink" href="#obtaining-instances-of-slotted-page" title="Permalink to this headline">¶</a></h3>
<p>The actual implementation of the Slotted Page is not visible to the
outside world. The Slotted Page Manager module <em>registers</em> the
implementation of SlottedPage to the Object Registry. This enables
client modules to obtain new instances of SlottedPage without having
to know how this is implemented. Following snippet of code
illustrates this:</p>
<div class="highlight-python"><pre>SlottedPageMgr spmgr = new SlottedPageMgrImpl(objectFactory);
SlottedPage page = (SlottedPage)
  pageFactory.getInstance(spmgr.getPageType(), new PageId());</pre>
</div>
<p>Note that the PageFactory is able to instantiate the appropriate
Page type using the typecode (<tt class="docutils literal"><span class="pre">spmgr.getPageType()</span></tt>) assigned
to the implementation by the SlottedPageManager module.</p>
<p>In most cases, clients do not actually invoke the PageFactory as
shown above. Instead it is more common to specify the page type when
a container is first created; this ensures that the Buffer Manager
module can instantiate the correct page type automatically. Here is
an example of how to do this:</p>
<div class="highlight-python"><pre>// Create the container and specify SlottedPage as the page
// type.
spaceMgr.createContainer(trx, name, containerId, spacebits,
  extentSize, spmgr.getPageType());

// Fix page 5
BufferAccessBlock bab =
  bufmgr.fixExclusive(new PageId(containerId, 5), false, -1, 0);

// Get access to the page.
SlottedPage page = (SlottedPage) bab.getPage();</pre>
</div>
<p>In the example above, the Space Manager module formats all data
pages in the specified container as SlottedPage. This ensures that
when the client module accesses the page via the Buffer Manager,
the correct page type is automatically instantiated.</p>
</div>
<div class="section" id="inserting-or-updating-records">
<h3><a class="toc-backref" href="#id190">Inserting or updating records</a><a class="headerlink" href="#inserting-or-updating-records" title="Permalink to this headline">¶</a></h3>
<p>The SlottedPage interface supports two insert modes. In the
replace mode, the new record will replace any existing record at
the same Slot. If replace mode is false, the new record will cause
existing records to be shifted to the right to make space for the
new record.</p>
<div class="highlight-python"><pre>boolean replaceMode = false;
// Insert item1 at Slot 0
page.insertAt(0, item1, replaceMode);
// Insert item0 at Slot 0
page.insertAt(0, item0, replaceMode);
// Now item1 is at Slot 1</pre>
</div>
<p>When invoking <tt class="docutils literal"><span class="pre">SlottedPage.insertAt()</span></tt>, the SlotNumber must be
between 0 and <tt class="docutils literal"><span class="pre">SlottedPage.getNumberOfSlots()</span></tt>.</p>
</div>
<div class="section" id="deleting-records">
<h3><a class="toc-backref" href="#id191">Deleting records</a><a class="headerlink" href="#deleting-records" title="Permalink to this headline">¶</a></h3>
<p>As mentioned before, there are two types of delete.
The first type removes the record but does not disturb the
Slot Numbers. Example:</p>
<div class="highlight-python"><pre>// Insert at slot 0
page.insertAt(0, item0, true);
// Insert at slot 1
page.insertAt(1, item1, true);
// Delete slot 0
page.delete(0)
// Slot 1 still holds item1</pre>
</div>
<p>The second mode is called purge, and in this mode,
records to the right of the deleted Slot are moved
left to fill up the hole. Example:</p>
<div class="highlight-python"><pre>// Insert at slot 0
page.insertAt(0, item0, true);
// Insert at slot 1
page.insertAt(1, item1, true);
// Delete slot 0
page.purge(0)
// Slot 0 now holds item1</pre>
</div>
</div>
<div class="section" id="accessing-records">
<h3><a class="toc-backref" href="#id192">Accessing records</a><a class="headerlink" href="#accessing-records" title="Permalink to this headline">¶</a></h3>
<p>The <tt class="docutils literal"><span class="pre">SlottedPage.getNumberOfSlots()</span></tt> method returns the number
of slots in the page. To access a slot, you invoke <tt class="docutils literal"><span class="pre">SlottedPage.get()</span></tt>;
you must supply the correct <tt class="docutils literal"><span class="pre">Storable</span></tt> object
type as the second parameter.</p>
<div class="highlight-python"><pre>// Get the record at Slot 1 as a StringItem.
page.get(1, new StringItem());</pre>
</div>
</div>
<div class="section" id="miscellaneous-operations">
<h3><a class="toc-backref" href="#id193">Miscellaneous operations</a><a class="headerlink" href="#miscellaneous-operations" title="Permalink to this headline">¶</a></h3>
<p>It is possible to assign to each Slot a set of flags.
Upto 16 bits can be accomodated.</p>
<div class="highlight-python"><pre>// Get the flags for Slot 0
int flags = page.getFlags(0);
// Update the flags for Slot 0
page.setFlags(0, (short)(flags | 1));</pre>
</div>
<p>The total number of Slots in the page is returned by
the method <tt class="docutils literal"><span class="pre">getNumberOfSlots()</span></tt>. To test whether a particular Slot is deleted, you can use
the method <tt class="docutils literal"><span class="pre">isSlotDeleted()</span></tt>.
There are a few methods that provide space usage data.</p>
</div>
</div>
<div class="section" id="index-manager">
<h2><a class="toc-backref" href="#id194">Index Manager</a><a class="headerlink" href="#index-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="id36">
<h3><a class="toc-backref" href="#id195">Overview</a><a class="headerlink" href="#id36" title="Permalink to this headline">¶</a></h3>
<p>The Index Manager module is responsible for implementing search structures
such as BTrees. Indexes are used to enforce primary key constraint and unique
constraints in tables, as well as for ensuring speedy retrieval of data.</p>
</div>
<div class="section" id="challenges-with-b-tree-concurrency">
<h3><a class="toc-backref" href="#id196">Challenges with B-Tree Concurrency</a><a class="headerlink" href="#challenges-with-b-tree-concurrency" title="Permalink to this headline">¶</a></h3>
<p>It is challenging to implement a B-Tree that supports high concurrency and
is also recoverable. The problem occurs because B-Tree traversals occur
top-down, whereas the tree grows bottom-up using page splits that are
propagated up the tree.</p>
<p>In the following discussion, the term SMO is used to refer to modifications
to a B-Tree that causes the Tree&#8217;s structure to change. By structure we mean
the relationships that exist between the nodes in the tree, such as parent-
child and sibling relationships.</p>
<p>The key ideas that enable concurrent updates to B-Trees are:</p>
<ol class="arabic simple">
<li>Short term locks must be used to prevent interactions between concurrent
updaters and traversers to ensure that each process gets a
structurally consistent (but not necessarily the same) view of the
B-Tree. A considerable amount of research has been devoted to ways of
reducing the scope of locking to increase concurrency. Worst case
is that the entire Tree must be exclusively locked during an SMO.</li>
<li>In B+Tree trees (a variation of B-Tree), all keys are maintained in the
leaf pages and the index nodes act as navigation aids. In such trees,
completed structural changes to the B-Tree need not be undone even when
transactions that initiated them roll back. Only incomplete structural
changes must be undone because they will corrupt the B-Tree.</li>
<li>Although structural updates occur bottom up, locking must always
be top-down. Maximum concurrency is obtained when structural changes
can be propagated bottom-up without obtaining locks at multiple
levels of the tree.</li>
</ol>
<div class="section" id="survey-of-algorithms">
<h4><a class="toc-backref" href="#id197">Survey of algorithms</a><a class="headerlink" href="#survey-of-algorithms" title="Permalink to this headline">¶</a></h4>
<p>A popular approach to improving concurrency is based on locking
subsets of the Tree top-down during an SMO. For example, if it becomes
necessary to split a page, the program gives up any locks on
the page to be split, and traverses down the tree from root, obtaining
exclusive locks on nodes while moving down the tree. If a node is
encountered which is &#8220;safe&#8221;, i.e., has sufficient space for accomodating
a split key, then locks on higher level nodes may be released. This
process continues until the leaf node is found that is to be split. In
the worst case scenario the entire path from the root node to the leaf
node will be locked exclusively. Having obtained all the locks, the
inserter can proceed splitting the leaf node and propagating the
change up the tree.</p>
<p>An undesirable feature of this method is that locks are obtained at
multiple levels of the tree, which is bad for concurrency.</p>
<p>ARIES/IM <a class="reference internal" href="#moha-92">[MOHA-92]</a> algorithm tries to avoid locking pages at more than one
level simultaneously. SMOs are performed bottom-up rather than top-down for
maximum concurrency, but a Tree Lock is used to serialize SMO operations.
This means that only one SMO operation can be active at any point in time,
but operations that do not cause SMOs, can proceed concurrently. The
ARIES/IM algorithm supports key deletions and node consolidations.</p>
<p>Several other approaches to the problem of concurrency in B-Trees are
based on the seminal work done by Lehman and Yao in <a class="reference internal" href="#lehman-81">[LEHMAN-81]</a>. The B-Link
tree structure described by Lehman and Yao has following features:</p>
<ul class="simple">
<li>Nodes are linked to each other from left to right at each level of the Tree.</li>
<li>Each key in an index node has an associated child pointer which points to
a subtree containing keys that are guaranteed to be less or equal to the
key value.</li>
<li>Leaf nodes have an extra key that is known as the <em>high key</em> - all keys in
the leaf node are guaranteed to be less or equal to the high key.</li>
<li>The algorithm does not support consolidation or deletion of nodes. Once
created, the nodes continue to exist. Key deletes are handled by simply
removing keys from the leaf nodes - hence the need for a <em>high key</em> as
an upper-bound for the key-range within a leaf node. Leaf nodes are allowed
to become empty (except for the high key which can never be deleted).</li>
<li>Page splits always result in a new sibling to be created on the
right.</li>
<li>Page splits always update the sibling pointer first, before updating
the parent node. The page split and the sibling pointer update is handled
as an atomic action to ensure that no two processes can ever see
the Tree in a state where two adjacent nodes are not linked in this way.</li>
</ul>
<p>The main idea is that while an a page split is in progress, there is
a short time window during which the parent lacks a pointer to the
newly allocated child node. During this time window, the newly allocated node
can be reached via the sibling node to its left.</p>
<p>During navigation, if the search key exceeds the highest value in
the node, it indicates that the tree structure has changed, and the
traversal must move right to the sibling node to find the search key.</p>
<p>The concurrency of a B-link Tree is improved because in the worst case
only three nodes need to be locked during a page split, and
page splits are propagated bottom-up rather than top-down.</p>
<a class="reference external image-reference" href="_images/lehman-split.png"><img alt="_images/lehman-split.png" src="_images/lehman-split.png" /></a>
<p>The diagram above shows the worst case locking, when original
parent node, its new sibling, and the left child are all locked
before the new link to the right sibling is inserted.</p>
</div>
<div class="section" id="limitations-of-lehman-and-yao-b-link-trees">
<h4><a class="toc-backref" href="#id198">Limitations of Lehman and Yao B-link Trees</a><a class="headerlink" href="#limitations-of-lehman-and-yao-b-link-trees" title="Permalink to this headline">¶</a></h4>
<p>Lehman and Yao assumed that each process that accesses a node
would read its own copy of the page. In most DBMS implementations,
this is not true. Pages are shared between processes via the
Buffer Manager. Therefore readers must lock pages in shared mode
before accessing them.</p>
<p>Deletions do not support merging of nodes because when propagating
a key split up the tree, the algorithm relies on always being
able to move right from the current parent node to find the correct
node where the child link and split key needs to be
inserted.</p>
<p>Suggestion is to use offline process that locks the entire tree
in order to compact the tree.</p>
<p>The algorithm does not consider recovery.</p>
</div>
<div class="section" id="recoverable-b-link-trees">
<h4><a class="toc-backref" href="#id199">Recoverable B-Link Trees</a><a class="headerlink" href="#recoverable-b-link-trees" title="Permalink to this headline">¶</a></h4>
<p>The individual page split operations in a B-Link Tree can be made
atomic by using the nested top action features of ARIES. These atomic
actions must be independent of regular transactions and must not be
undone even if the transaction that triggered them is aborted.</p>
<p>The difficult bit is to ensure that the parent nodes are properly
updated even if there is a system crash, say between the split
occuring at leaf level and it being propagated to the level above.</p>
<p>In <a class="reference internal" href="#davi-92">[DAVI-92]</a>, the authors provide a solution to this problem.
During tree traversals, it is possible to detect that a node
lacks a pointer to it from the parent. When this is detected,
an action can be initiated to add the missing link into the
parent node.</p>
</div>
<div class="section" id="b-tree-algorithm-in-apache-derby">
<h4><a class="toc-backref" href="#id200">B-Tree algorithm in Apache Derby</a><a class="headerlink" href="#b-tree-algorithm-in-apache-derby" title="Permalink to this headline">¶</a></h4>
<p>In <a class="reference external" href="http://db.apache.org/derby/papers/btree_package.html">Apache Derby</a>, when an inserter finds during a page split that
that it is unable to promote the discriminator key into the parent
node because the parent node is full, it releases all locks, and
starts a new traversal from the root, splitting all nodes that are
too full to accomodate the discriminator key. This is done top-down,
and may esult in moe page splits that needed, but the assumption is
that the nodes would have to be split eventually anyway.</p>
</div>
<div class="section" id="simpledbm-b-link-tree">
<h4><a class="toc-backref" href="#id201">SimpleDBM B-link Tree</a><a class="headerlink" href="#simpledbm-b-link-tree" title="Permalink to this headline">¶</a></h4>
<p><a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> currently provides a B-Link Tree Index implementation, based
upon algorithms described in <a class="reference internal" href="#jaluta-05">[JALUTA-05]</a>.
These algorithms combine the idea of short atomic actions, as in <a class="reference internal" href="#davi-92">[DAVI-92]</a>,
with top-down detection and correction of page overflow and underflow
conditions. Unlike previous algorithms, these algorithms handle deletes
uniformly as inserts, and automatically merge nodes as they become
empty.</p>
<p>There are some variations from the published algorithms, noted at appropriate
places within the code, and described below.</p>
</div>
</div>
<div class="section" id="structure-of-the-b-link-tree">
<h3><a class="toc-backref" href="#id202">Structure of the B-link Tree</a><a class="headerlink" href="#structure-of-the-b-link-tree" title="Permalink to this headline">¶</a></h3>
<p>The tree is contained in a container of fixed size pages. The
first page (pagenumber = 0) of the container is a header page. The second
page (pagenumber = 1) is the first space map page. These pages are
common to all containers that are managed by the Free Space Manager
module.</p>
<p>The third page (pagenumber = 2) is  allocated as the root page of the
tree. The root page never changes.</p>
<a class="reference external image-reference" href="_images/blink-tree-structure.jpg"><img alt="_images/blink-tree-structure.jpg" src="_images/blink-tree-structure.jpg" /></a><p>Pages at all levels are linked to their right siblings.
In leaf pages, an extra item called the high key is present. In index
pages, the last key acts as the highkey. All keys in a page are guaranteed
to be &lt;= than the highkey. Note that in leaf pages the highkey may not be
the same as the last key in the page.</p>
<p>The reason for the extra high key in leaf pages is that the high key
defines the key space contained within the leaf page, and does not change
when the keys within the leaf page are deleted. The highest key in the
leaf page cannot be used as the high key because the high key can only change
through page split, redistribute or merge (SMO) activities, whereas the highest
key may be deleted outside of these operations, for example, as part of
a delete key operation.</p>
<p>In index pages, each key is associated with a pointer to a child page. The
child page contains keys &lt;= to the key in the index page.</p>
<p>A direct child can be accessed from the parent by following a child pointer.
An indirect child is accessed via the direct child&#8217;s right sibling pointer.</p>
<a class="reference external image-reference" href="_images/node-direct-indirect.png"><img alt="_images/node-direct-indirect.png" src="_images/node-direct-indirect.png" /></a>
<p>The highkey of the child page will match the index key if the child
is a direct child.
The highkey of the child page will be &lt; than the index key if the
child has a sibling that is an indirect child.</p>
<p>All pages other than root must have at least two items (excluding
the highkey in leaf pages).</p>
<p>The root node is allowed to have a right sibling. Eventually, such a
situation is resolved by increasing the tree&#8217;s height. See <a class="reference internal" href="#increase-tree-height-operation">Increase Tree
Height Operation</a> for more information.</p>
<p>The rightmost key at any level is a special key containing logical
INFINITY. Initially, the empty tree contains this key only. As the tree
grows through splitting of pages, the INFINITY key is carried
forward to the rightmost pages at each level of the tree. This key can
never be deleted from the tree.</p>
</div>
<div class="section" id="structure-of-nodes">
<h3><a class="toc-backref" href="#id203">Structure of Nodes</a><a class="headerlink" href="#structure-of-nodes" title="Permalink to this headline">¶</a></h3>
<div class="section" id="id42">
<h4><a class="toc-backref" href="#id204">Overview</a><a class="headerlink" href="#id42" title="Permalink to this headline">¶</a></h4>
<p>Nodes at each level of the tree are linked from left to right.
The link of the rightmost node at a particular level is always set
to null.</p>
</div>
<div class="section" id="leaf-nodes">
<h4><a class="toc-backref" href="#id205">Leaf Nodes</a><a class="headerlink" href="#leaf-nodes" title="Permalink to this headline">¶</a></h4>
<p>Leaf nodes have following structure:</p>
<a class="reference external image-reference" href="_images/leaf-node.png"><img alt="_images/leaf-node.png" src="_images/leaf-node.png" /></a>
<div class="highlight-python"><pre>[header] [item1] [item2] ... [itemN] [highkey]

item[0] = header
item[1,header.KeyCount-1] = keys
item[header.keyCount] = high key</pre>
</div>
<p>The highkey in a leaf node is an extra item, and may or may not be
the same as the last key [itemN] in the page. Operations that change the
highkey in leaf pages are Split, Merge and Redistribute. All keys in the
page are guaranteed to be &lt;= highkey.</p>
</div>
<div class="section" id="index-nodes">
<h4><a class="toc-backref" href="#id206">Index Nodes</a><a class="headerlink" href="#index-nodes" title="Permalink to this headline">¶</a></h4>
<p>Index nodes have following structure:</p>
<div class="highlight-python"><pre>[header] [item1] [item2] ... [itemN]
item[0] = header
item[1,header.KeyCount] = keys</pre>
</div>
<p>The last key is also the highkey.
Note that the rightmost index page at any level has a special
key as the highkey - this key has a value of INFINITY.</p>
<p>Each item in an index key contains a pointer to a child page.
The child page contains keys that are &lt;=
than the item key.</p>
</div>
<div class="section" id="limits">
<h4><a class="toc-backref" href="#id207">Limits</a><a class="headerlink" href="#limits" title="Permalink to this headline">¶</a></h4>
<p>The largest key cannot exceed 1/8th size of the page. The published
algorithm requires a key to be smaller than 1/6th of a page.</p>
<p>Each page other than root must have at least two keys.</p>
</div>
</div>
<div class="section" id="key-differences-from-published-algorithm">
<h3><a class="toc-backref" href="#id208">Key Differences from published algorithm</a><a class="headerlink" href="#key-differences-from-published-algorithm" title="Permalink to this headline">¶</a></h3>
<div class="section" id="support-for-non-unique-indexes">
<h4><a class="toc-backref" href="#id209">Support for Non-Unique indexes</a><a class="headerlink" href="#support-for-non-unique-indexes" title="Permalink to this headline">¶</a></h4>
<p>The published algorithm assumes a unique index. <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> implementation
supports both unique and non-unique indexes. In non-unique indexes, a
key/location pair is always the unit of comparison, whereas in unique
indexes, only key values are used. There are some differences in how
locking is handled for a unique index versus a non-unique index.</p>
</div>
<div class="section" id="handling-of-storage-map">
<h4><a class="toc-backref" href="#id210">Handling of storage map</a><a class="headerlink" href="#handling-of-storage-map" title="Permalink to this headline">¶</a></h4>
<p>The published algorithm assumes a single page 0 that contains a bit vector
showing the allocated/unallocated status of all pages. In <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>
implementation space allocation is managed using free space pages which
are arranged in a linked list and are dynamic.</p>
<p>There is an important concurrency improvement related to handling of the space
map. See <a class="reference internal" href="#diby-05">[DIBY-05]</a> for further details.</p>
</div>
<div class="section" id="variable-length-keys">
<h4><a class="toc-backref" href="#id211">Variable length keys</a><a class="headerlink" href="#variable-length-keys" title="Permalink to this headline">¶</a></h4>
<p>The implementation differs from the published algorithm in how it
determines whether a page is &#8220;about to underflow&#8221; or &#8220;about to overflow&#8221;. It
considers any page with minimum keys (1 for root, and 2 for all other pages) as
about to underflow. It checks the available space for the key being inserted to
determine whether the page is about to overflow.</p>
</div>
<div class="section" id="page-split-operation">
<h4><a class="toc-backref" href="#id212">Page Split operation</a><a class="headerlink" href="#page-split-operation" title="Permalink to this headline">¶</a></h4>
<p>A page split operation takes a node and splits it into two.
A new node is allocated and linked to the old node. This is
shown in the example below.</p>
<p>Here&#8217;s an example of a leaf node. Note the presence of the
extra high key.</p>
<a class="reference external image-reference" href="_images/split-leaf.png"><img alt="_images/split-leaf.png" src="_images/split-leaf.png" /></a>
<p>When the node is split, the keys are divided between the old node
and a newly allocated node. The old node&#8217;s right field is set to
point to the newly allocated right sibling. Note that the high key
changes in the old node and is set to be the same as the highest
key in the node. This may later on change as keys are deleted from
the node.</p>
<a class="reference external image-reference" href="_images/split-leaf-2.png"><img alt="_images/split-leaf-2.png" src="_images/split-leaf-2.png" /></a>
<p>The splitting of an index node is similar, except that the
extra high key is not present.</p>
<a class="reference external image-reference" href="_images/split-nonleaf.png"><img alt="_images/split-nonleaf.png" src="_images/split-nonleaf.png" /></a>
<a class="reference external image-reference" href="_images/split-nonleaf-2.png"><img alt="_images/split-nonleaf-2.png" src="_images/split-nonleaf-2.png" /></a>
<p>The Split Operation differs from the published algorithm in following ways:</p>
<ol class="arabic simple">
<li>Page allocation is logged as redo-undo.</li>
<li>Space map page latch is released prior to any other exclusive latch.</li>
<li>The split is logged as Muli Page Compensation record, with undoNextLsn
set to the LSN prior to the page allocation log record.</li>
<li>Information about space map page is stored in new page.</li>
<li>The total space occupied by keys as an indicator of key
space. For example, when finding the median
key, <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> sums up key lengths to decide where to split.</li>
</ol>
<p>When implementing the Split operation it became necessary to
enhance the transaction manager to support multi-page redo records - ie
- one redo record containing data for multiple pages. The published
ARIES algorithms do not cater for this.</p>
<p>The published algorithm does not state this requirement but assumes
that the transaction manager supports multi-page redo.</p>
</div>
<div class="section" id="merge-operation">
<h4><a class="toc-backref" href="#id213">Merge Operation</a><a class="headerlink" href="#merge-operation" title="Permalink to this headline">¶</a></h4>
<p>The Merge Operation is the opposite of the Split operation. It joins
two existing nodes to create a single node.</p>
<p>The implementation differs from published algorithm in its management of
space map update. In the interests of high concurrency, the space map
page update is handled as a separate redo only action which is logged
after the merge operation.</p>
<p>If this space map update log record does not survive a system crash,
then the page will end up appearing allocated. However the actual page will
be marked as deallocated, and hence can be reclaimed later on, although
this is not implemented.</p>
<p>The Merge Operation is logged as a Multi-Page Redo only record.</p>
</div>
<div class="section" id="link-operation">
<h4><a class="toc-backref" href="#id214">Link Operation</a><a class="headerlink" href="#link-operation" title="Permalink to this headline">¶</a></h4>
<p>The Link Operation creates a link from a parent node to a child node.
Following diagrams illustrate the link operation.</p>
<p>Before the link operation:</p>
<a class="reference external image-reference" href="_images/link.png"><img alt="_images/link.png" src="_images/link.png" /></a>
<p>After the link operation:</p>
<a class="reference external image-reference" href="_images/link-2.png"><img alt="_images/link-2.png" src="_images/link-2.png" /></a>
<p>The implementation differs slightly from the published algorithm.
The psuedo code for the implementation is shown below.</p>
<div class="highlight-python"><pre>v = highkey of RightNode
u = highkey of LeftNode
Link(ParentNode, LeftNode, RightNode) {
  upgrade-latch(ParentNode);
  n = new index record (u, LeftNode.pageno);
  lsn = log(&lt;unlink, ParentNode, n, LeftNode.pageno, RightNode.pageno&gt;);
  find index record with child pointer = LeftNode.pageno in ParentNode;
  change the child pointer of above to RightNode.pageno;
  insert new index record n before above index record.
  ParentNode.pageLsn = lsn;
  downgrade-latch(ParentNode);
}</pre>
</div>
</div>
<div class="section" id="unlink-operation">
<h4><a class="toc-backref" href="#id215">Unlink Operation</a><a class="headerlink" href="#unlink-operation" title="Permalink to this headline">¶</a></h4>
<p>The Unlink Operation is the reverse of the Link operation.</p>
<p>The implementation differs slightly from the published algorithm.
The psuedo code is shown below.</p>
<div class="highlight-python"><pre>Unlink(ParentNode, LeftNode, RightNode) {
  upgrade-latch(P);
  lsn = log(&lt;unlink, ParentNode, LeftNode.pageno, RightNode.pageno&gt;);
  in ParentNode delete the index record with child pointer
     set to LeftNode.pageno;
  change the child pointer of next index record to LeftNode.pageno;
  ParentNode.pageLsn = lsn;
  unfix(ParentNode);
}</pre>
</div>
</div>
<div class="section" id="redistribute-keys-operation">
<h4><a class="toc-backref" href="#id216">Redistribute Keys Operation</a><a class="headerlink" href="#redistribute-keys-operation" title="Permalink to this headline">¶</a></h4>
<p>The implementation of this differs from the published algorithm. It
moves one key from the overpopulated node to the sibling node,
rather than evenly redistributing the keys across the two
nodes.</p>
<p>For example, before the Redistribute Operation:</p>
<a class="reference external image-reference" href="_images/split-leaf-2.png"><img alt="_images/split-leaf-2.png" src="_images/split-leaf-2.png" /></a>
<p>After the Redistribute Operation:</p>
<a class="reference external image-reference" href="_images/redistribute.png"><img alt="_images/redistribute.png" src="_images/redistribute.png" /></a>
<p>The Redistribute Key operation is logged using a Multi-Page
redo only log record.</p>
</div>
<div class="section" id="increase-tree-height-operation">
<h4><a class="toc-backref" href="#id217">Increase Tree Height Operation</a><a class="headerlink" href="#increase-tree-height-operation" title="Permalink to this headline">¶</a></h4>
<p>The Increase Tree Height Operation is used to raise the height
of the tree. For this to occur, the root must have been split
previously and therefore must have a right sibling.</p>
<p>During this operation, a new node is allocated and the contents
of the rooot node copied to this new node. The root node is then
re-initialized to contain pointers to the new node as its left
child and the old right sibling as its right child.</p>
<p>For example, let us consider the following:</p>
<a class="reference external image-reference" href="_images/increase-height.png"><img alt="_images/increase-height.png" src="_images/increase-height.png" /></a>
<p>This is how it appears after the Increase Tree Height Operation:</p>
<a class="reference external image-reference" href="_images/increase-height-2.png"><img alt="_images/increase-height-2.png" src="_images/increase-height-2.png" /></a>
<p>The implementation differs from the published algorithm in following ways:</p>
<ol class="arabic simple">
<li>Page allocation is logged as redo-undo.</li>
<li>Space map page latch is released prior to any other exclusive latch.</li>
<li>The Increase Tree Height operatopn is logged as Muli Page
Compensation record, with undoNextLsn set to the LSN prior to the
page allocation log record.</li>
<li>There is no need to format the new page as pages are formatted
when they are first created.</li>
</ol>
</div>
<div class="section" id="decrease-tree-height-operation">
<h4><a class="toc-backref" href="#id218">Decrease Tree Height Operation</a><a class="headerlink" href="#decrease-tree-height-operation" title="Permalink to this headline">¶</a></h4>
<p>This differs from the published algorithm.</p>
<p>To increase concurrency, the  space map page update is logged after the
SMO as a separate redo only action. This improves concurrency because
the space map page latch is not held exclusively during the SMO. However,
it has the disadvantage that if the SMO survives a system crash, and the
log for the space map page updates does not survive,
then the page will remain allocated on the space map, even though it is no
longer in use. It is posible to identify deallocated pages by checking
the page flags for the BTreeNode but this is not implemented.</p>
<p>The Decrease Tree Height Operation is logged as Multi Page Redo only
log record.</p>
</div>
<div class="section" id="index-scans">
<h4><a class="toc-backref" href="#id219">Index Scans</a><a class="headerlink" href="#index-scans" title="Permalink to this headline">¶</a></h4>
<p>The published algorithm only considers the SERIALIZATION lock isolation
mode, but the implementation supports other lock modes. There are
differences in when and where locks are acquired and released under
various modes.</p>
</div>
<div class="section" id="simplified-algorithm-for-scans">
<h4><a class="toc-backref" href="#id220">Simplified Algorithm for Scans</a><a class="headerlink" href="#simplified-algorithm-for-scans" title="Permalink to this headline">¶</a></h4>
<p>The published algorithm has a complex fetch and fetchnext logic,
and attempts to handle both &gt; and &gt;= operators. The implementation
does not allow the operator to be specified. It automatically uses
&gt;= for the first fetch, and then &gt; than current key for subsequent
fetches.</p>
<p>The code for next key locking code is simplified. We don&#8217;t do all the
checks that are in the published algorithm. This means that there is a
greater chance that the tree will be rescanned.</p>
<p>The published fetch algorithm does not cater for UPDATEABLE cursors. In
general, the paper assumes that the B-Tree is standalone, and contains
data records. In <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>, and in most DBMS implementations, a
B-Tree index is a redundant structure - leaf pages contain pointers to
data records. The published algorithms are not always the best fit for
this. For example:</p>
<ol class="arabic simple">
<li>The algorithm suggests locking current key and next key during
Inserts and Deletes. In a DBMS, the current key is already locked
when an Insert or Delete is issued.</li>
<li>In a DBMS a fetch cursor is also used in UPDATE mode. For example,
when a DELETE or UPDATE SQL statement is issued, the records must
be fetched using UPDATE locks. Then the lock is upgraded to
EXCLUSIVE, and the key is deleted. In this scenario, we need to
cater for the fact that the current key may be deleted. Therefore,
when the fetch next call is issued, the cursor must be able to
detect that the key does not exist and rescan. These issues are
discussed in detail in <a class="reference internal" href="#moha-02">[MOHA-02]</a>.</li>
</ol>
<p><a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> does not implement the optimizations described in [MOHA-02].
Therefore, supposing all keys are deleted during the index scan, after the
first page, every delete will cause the tree to be scanned from root to
leaf. This can be avoided by using the technique described by Mohan.</p>
</div>
<div class="section" id="simpler-page-modification-checks">
<h4><a class="toc-backref" href="#id221">Simpler page modification checks</a><a class="headerlink" href="#simpler-page-modification-checks" title="Permalink to this headline">¶</a></h4>
<p>The implementation uses a simpler check to determine whether the
page has changed since last it was latched. This may cause unnecessary
traversals from root node.</p>
</div>
<div class="section" id="b-tree-index-is-a-secondary-structure">
<h4><a class="toc-backref" href="#id222">B-Tree index is a secondary structure</a><a class="headerlink" href="#b-tree-index-is-a-secondary-structure" title="Permalink to this headline">¶</a></h4>
<p>Unlike the published algorithm, where the B-Tree index holds the
database records in the leaf nodes, the implementation stores pointers
(Locations) to tuples (table rows).</p>
</div>
</div>
</div>
<div class="section" id="tuple-manager">
<h2><a class="toc-backref" href="#id223">Tuple Manager</a><a class="headerlink" href="#tuple-manager" title="Permalink to this headline">¶</a></h2>
<div class="section" id="overview-of-tuple-manager">
<h3><a class="toc-backref" href="#id224">Overview of Tuple Manager</a><a class="headerlink" href="#overview-of-tuple-manager" title="Permalink to this headline">¶</a></h3>
<p>The Tuple Manager module provides a low-level interface for
managing persistence of table rows. It is low-level in the sense that
this module has no knowledge of what is contained in a table row.
I use the term tuple instead of table row, but even this is not
the right term, as a tuple means a collection of attributes.</p>
<p>To the Tuple Manager, tuples are just blobs of data that can span
multiple pages. When a tuple is inserted for the first time, it
is assigned a unique Location, which is really an abstraction of
the ROWID concept in other databases. The Tuple Manager module
implements the Location interface, but other modules do not need
to know anything about the internal structure of these objects.</p>
<p>Like B-Tree indexes, tuples are stored in containers. A container
that is specialized for storing tuples is called a Tuple Container.
By design, only one type of tuple may be stored in a particular
container. In a higher level module, a tuple can be mapped to a
table row, and the container to a table.</p>
<p>The interface of Tuple Manager is made generic by ensuring that it
knows very little about tuples. Unfortunately, this means that
tuple updates cannot be handled efficiently, specially with regards
to logging, as the contents of the both before and after images of
the tuple must be logged. A possible optimisation would be to use
some form of binary diff algorithm to generate a change vector,
and store the change vector only in the log record. Another way is
to allow a callback method to calculate the difference between
the old and the new tuple.</p>
</div>
<div class="section" id="design-decisions">
<h3><a class="toc-backref" href="#id225">Design Decisions</a><a class="headerlink" href="#design-decisions" title="Permalink to this headline">¶</a></h3>
<p>Some of the implementation decisions are given below:</p>
<div class="section" id="tuple-inserts">
<h4><a class="toc-backref" href="#id226">Tuple Inserts</a><a class="headerlink" href="#tuple-inserts" title="Permalink to this headline">¶</a></h4>
<p>Tuple inserts are done in two stages. In the first stage,
a new Location is allocated and locked exclusively. Also, the
tuple data is inserted into the first page that will be used by the
tuple. The rest of the tuple data is inserted in the second stage. The
rationale for splitting the insert into two stages is to allow
the client to perform other operations in between, such as creating
Index keys.</p>
</div>
<div class="section" id="tuple-segmentation">
<h4><a class="toc-backref" href="#id227">Tuple Segmentation</a><a class="headerlink" href="#tuple-segmentation" title="Permalink to this headline">¶</a></h4>
<p>If a tuple is too large to fit into one page, it is broken into
chunks of <tt class="docutils literal"><span class="pre">TupleManagerImpl.TupleSegment</span></tt>. Each segment is inserted
into a page, and the segments are linked together in a singly linked
list. Since the segments are inserted in order, in the first pass the links
are not set, and the implementation has to revisit all the pages and update
the links between the segments. The last segment/page does not require
an update.</p>
<p>At the time of insert, the implementation tries to allocate as much space
as possible on each page. When a page is visited, an attempt is made to
reclaim any deleted segments within the page.</p>
</div>
<div class="section" id="tuple-deletes">
<h4><a class="toc-backref" href="#id228">Tuple Deletes</a><a class="headerlink" href="#tuple-deletes" title="Permalink to this headline">¶</a></h4>
<p>Deletes are logical, ie, the Tuple Segments are marked with a logical
delete flag. Space Map information is updated immediately, however. During
deletes, the links between the segments of a tuple are broken. This is
because the link is reused to store the tuple&#8217;s Location. Thus, it is
possible to determine the Location of a tuple from any of the deleted
segments. This is important because the tuple reclamation logic uses
locking to determine whether a logically deleted tuple can be physically
removed.</p>
<p>If the delete is undone, the links are restored.</p>
</div>
<div class="section" id="tuple-updates">
<h4><a class="toc-backref" href="#id229">Tuple Updates</a><a class="headerlink" href="#tuple-updates" title="Permalink to this headline">¶</a></h4>
<p>When tuples are updated, existing segments are updated with new data. If the
new tuple is longer than the old tuple, then additional segments are added.
The <tt class="docutils literal"><span class="pre">TupleInserter#completeInsert()</span></tt> interface is reused for this purpose.
No attempt is made to change the size of existing segments, even if there
is additional space available in the page. This is to keep the algorithm
simple. Also, segments are never released, even if the new tuple has
become smaller and does not occupy all the segments.</p>
<p>Note that due to the way this is implemented, more than one segment of
the same tuple can end up in the same page.</p>
<p>Since the structure of the tuple is opaque to this module, updates are not
very efficiently handled. Current implementation logs the full before and
after images of the tuple being updated. In future, this needs to be made
more efficient by using some mechanism to calculate the difference between
the old tuple and the new.</p>
</div>
<div class="section" id="space-reclamation">
<h4><a class="toc-backref" href="#id230">Space Reclamation</a><a class="headerlink" href="#space-reclamation" title="Permalink to this headline">¶</a></h4>
<p>Space used by deleted tuples is reclaimed when some other transaction visits
the affected page and tries to use the space. Locking is used to determine
whether the delete was committed. The actual physical removal of the tuple
segments are logged. Note that this method of determining whether a segment
can be released is conservative and sometimes results in segments being
retained even when they are no longer required. Why this happens will become
clear with an example. Suppose that a tuple that has 4 segments is deleted.
Each segment is marked deleted. Now, some transaction creates a new tuple,
reusing the Location of the deleted tuple. However, the new tuple may not
reuse all the segments used by the old tuple, in fact, only the first segment
is guaranteed to be reused. As a result of the tuple insert, the
Location gets exclusively locked. If this transaction or any other transaction
encounters the remaining segments that are marked deleted, the reclamation
logic will incorrectly assume that the delete is still uncommitted, because
the lock on the location will fail. The segments wil get eventually reused,
when the transaction that locked the tuple commits.</p>
</div>
<div class="section" id="tuple-segment-structure">
<h4><a class="toc-backref" href="#id231">Tuple Segment Structure</a><a class="headerlink" href="#tuple-segment-structure" title="Permalink to this headline">¶</a></h4>
<p>Each Tuple segment contains three fields.</p>
<dl class="docutils">
<dt>nextPageNumber</dt>
<dd>Used only in segmented tuples. Normally, points to the location of
next segment. If a tuple is deleted, this is updated to the page
number of the first segment.</dd>
<dt>nextSlotNumber</dt>
<dd>Used only in segmented tuples. Normally, points to the location of
next segment. If a tuple is deleted, this is updated to the slot
number of the first segment.</dd>
<dt>data</dt>
<dd>Data in this segment.</dd>
</dl>
</div>
<div class="section" id="free-space-information">
<h4><a class="toc-backref" href="#id232">Free Space Information</a><a class="headerlink" href="#free-space-information" title="Permalink to this headline">¶</a></h4>
<p>Both BTrees and Tuple Containers need free space management. By
free space management we mean the process of identifying pages
where new data can go. In the case of B-Trees, <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> uses
space map pages that use one bit per page. This is okay, because in
a BTree, a page is either allocated or not.</p>
<p>In case of Tuple Containers, I am using space map pages that use
two bits to store the space information for a single page. This means
that we can track the following states: full (3), two-thirds full
(2), one-third full (1), and empty (0). Initially pages start out
empty, but when they are used, their status changes as required.</p>
<p>There are a couple of issues related to space management that
merit discussion. Unfortunately, there are very few papers that
go into all the details. Couple of very useful papers are
<a class="reference internal" href="#moha-94">[MOHA-94]</a> and <a class="reference internal" href="#carey-96">[CAREY-96]</a>.</p>
<p>The first issue is how to handle deletes. There are two options.</p>
<p>The first option is to delete a tuple physically and update space
map page to reflect the change. However, this poses the problem that
if the transaction aborts and the tuple needs to be restored,
then the restore will fail if some other transaction uses up the
released space in the meantime. To prevent this, some extra
information needs to be stored in the page to indicate that
although the tuple has been deleted, its space is reserved, and
cannot be used by any other transaction. One possible approach is
to store the transaction id and the amount of space reserved using
the space previously occupied by the tuple. If the tuple occupied
more than one page, then space must be reserved on all affected pages,
since otherwise, when the tuple is to be restored, the pages
may no longer have space to hold the tuple data. If logical undo
is implemented, then it is possible to avoid reserving space in
pages other than the first page, because a logical undo will
allow new pages to be commissioned if necessary to accomodate
the restored tuple. Since the tuple&#8217;s unique id (Location) is bound
to the first page, this page must always have space available
for the tuple to be restored.</p>
<p>If as suggested above, the space map information is updated as
soon as the tuple is deleted, then other transactions looking
for free space may end up visiting the pages that have been affected
by the tuple delete. However, those transactions may discover
when they access the page, that space is not actually available.
As a solution to this problem, the space map page update
could be deferred until the tuple delete is known to have
been committed. However, this would be inefficient, as the
transaction that performs the delete will have to visit all pages
affected by deleted tuples at commit time, and update the
free space map information for these pages.</p>
<p>The space map update could also be delegated to the next
transaction that needs the space. The problem with this is that
if the page remains marked as fully allocated, then no other
transaction will visit that page unless the tuples on the
page need to be updated. There is the risk that the tuple
space will never be reclaimed.</p>
<p>The problem of unnecessary visits to a page containing reserved
space can be avoided by techniques described in <a class="reference internal" href="#carey-96">[CAREY-96]</a>. This
involves maintaining a cache of recently used pages and avoiding
scanning of the free space map as long as there is candidate
page available in the cache. When a page is affected by
a tuple delete, it is added to the cache provided that its
total free space, including the space reserved for deleted tuple,
is greater than the fullest page in the cache. If a transaction
visits such a page and is unable to use the reserved space,
it removes the page from the cache.</p>
<p>In summary then, the preferred option appears to be to update
the space map information as soon as the tuple is deleted.</p>
<p>Physically deleting tuples affects the amount of logging
that must be performed. Since the tuple&#8217;s data is removed,
the log must contain the entire contents of the deleted tuple.
Similarly, when undoing the delete, the Compensation log
record must again contain the full content of the tuple.
Thus the tuple data gets logged twice potentially,
once when the delete occurs, and again if the transaction
aborts.</p>
<p>This brings us to the second option, which is to use
logical deletes. In this solution, the tuple remains as
is, but is marked as deleted. No space reservation is
needed, as the tuple still exists. The space map
information is updated as before, that is, at the time
of tuple being deleted. Using logical deletes makes
undo of such deletes a simple matter of resetting
the deleted flag. Logging overhead is substantially
reduced.</p>
<p>With logical deletes, however, none of the space can
be released prior to the transaction commit. In contrast,
with physical deletes, if logical undo is implemented,
at least some of the space can be immediately released.</p>
<p>Whether logical or physical deletes are used, in both
cases, we still have the issue of how to inform other
transactions that the tuple space is still needed. In both
cases, the solution is the same. The Lock Manager can
be used to ascertain whether the deleted tuple is still
locked. If not, then the transaction can infer that tuple
delete has been committed. The Lock Manager solution
works even if the ID of the transaction that deleted the
tuple is unknown, as it relies upon the tuple&#8217;s Location
only. If each tuple is tagged with the ID of the last
transaction that updated the tuple, then it would be
possible to directly query the transaction table for
the status of the transaction. However in this case,
the system would have to maintain the status of all
transactions, even those that have committed or aborted.
<a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a> maintains the status of only active transactions,
and also does not tag tuples with the IDs of transactions.
Hence, it is appropriate to use the Lock Manager solution
in <a class="reference external" href="http://www.simpledbm.org">SimpleDBM</a>.</p>
</div>
<div class="section" id="latch-ordering">
<h4><a class="toc-backref" href="#id233">Latch Ordering</a><a class="headerlink" href="#latch-ordering" title="Permalink to this headline">¶</a></h4>
<p>If both data page and free space map page need to be
updated, then the latch order is data page first, and
then free space map page while holding the data page
latch.</p>
</div>
<div class="section" id="logging-of-space-map-page-updates">
<h4><a class="toc-backref" href="#id234">Logging of Space Map Page updates</a><a class="headerlink" href="#logging-of-space-map-page-updates" title="Permalink to this headline">¶</a></h4>
<p>As per <a class="reference internal" href="#moha-94">[MOHA-94]</a>, space map pages should be logged using
redo only log records. During normal processing, the
data page update is logged first followed by the space
map page update. During undo processing, the space map
page update is logged first, followed by data page
update. Note that this does not change the latch
ordering.</p>
<table class="docutils citation" frame="void" id="astra-76" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[ASTRA-76]</td><td>M.M.Astrahan, M.W.Blasgen, D.D.Chamberlin,
K.P.Eswaran, J.N.Gray, P.P.Griffiths, W.F.King, R.A.Lorie,
P.R.McJones, J.W.Mehl, G.R.Putzolu, I.L.Traiger, B.W.Wade
AND V.Watson. System R: Relational Approach to Database
Management, ACM, Copyright 1976, ACM Transactions on
Database Systems, Vol 1, No. 2, June 1976, Pages 97-137.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="jaluta-05" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id40">[JALUTA-05]</a></td><td>Ibrahim Jaluta, Seppo Sippu and Eljas Soisalon-Soininen.
Concurrency control and recovery for balanced B-link trees.
The VLDB Journal, Volume 14, Issue 2 (April 2005),
Pages: 257 - 277, ISSN:1066-8888.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="lehman-81" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id38">[LEHMAN-81]</a></td><td>Philip L. Lehman, S. Bing Yao:
Efficient Locking for Concurrent Operations on B-Trees.
ACM Trans. Database Syst. 6(4): 650-670(1981)</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="diby-05" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id43">[DIBY-05]</a></td><td>Dibyendu Majumdar: Space Management in B-Link Trees. 2005.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="moha-02" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id44">[MOHA-02]</a></td><td>Mohan, C. An Efficient Method for Performing Record Deletions
and Updates Using Index Scans
(<a class="reference external" href="http://www.almaden.ibm.com/u/mohan/DelIScan.pdf">http://www.almaden.ibm.com/u/mohan/DelIScan.pdf</a>),
Proc. 28th International Conference on Very Large Databases, Hong Kong,
August 2002.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="baye-72" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[BAYE-72]</td><td>Rudolf Bayer, Edward M. McCreight. Organization and
Maintenance of Large Ordered Indices. Acta Inf. 1: 173-189 (1972).</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="comer" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[COMER]</td><td>Douglas Comer. The Ubiquitous B-Tree. ACM Computing Surveys.
11(2): 121-137.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="moha-92" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id37">[MOHA-92]</a></td><td>C.Mohan and Frank Levine. ARIES/IM: an efficient and
high concurrency index management method with write-ahead
logging. ACM SIGMOD Record. V21 N2, P371-380, June 1 1992.
A longer version of the paper can be found at:
<a class="reference external" href="http://www.almaden.ibm.com/u/mohan/RJ6846.pdf">http://www.almaden.ibm.com/u/mohan/RJ6846.pdf</a></td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="davi-92" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[DAVI-92]</td><td><em>(<a class="fn-backref" href="#id39">1</a>, <a class="fn-backref" href="#id41">2</a>)</em> David Lomet and Betty Salzburg. Access method
concurrency with recovery. ACM SIGMOD, V21 N2, p351-360, June 1 1992.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="aries" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id30">[ARIES]</a></td><td>C. Mohan, D. Haderle, B. Lindsay, H. Pirahesh and P.
Schwarz. ARIES: A Transaction Recovery Method Supporting Fine-Granularity
Locking and Partial Rollbacks Using Write-Ahead Logging.
ACM Transactions on Database Systems, 17(1):94-162, March 1992.
Also, Readings in Database Systems, Third Edition, 1998.
Morgan Kaufmann Publishers.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="jgray" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[JGRAY]</td><td><em>(<a class="fn-backref" href="#id23">1</a>, <a class="fn-backref" href="#id24">2</a>, <a class="fn-backref" href="#id31">3</a>, <a class="fn-backref" href="#id32">4</a>)</em> Transaction Processing: Concepts and Techniques, by Jim Gray
and Andreas Reuter</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="moha-94" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[MOHA-94]</td><td><em>(<a class="fn-backref" href="#id45">1</a>, <a class="fn-backref" href="#id48">2</a>)</em> C.Mohan and D.Haderle. Algorithms for Flexible Space Management
in Transaction Systems Supporting Fine-Granularity Locking.
In Proceedings of the International Conference on Extending
Database Technology, March 1994.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="carey-96" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label">[CAREY-96]</td><td><em>(<a class="fn-backref" href="#id46">1</a>, <a class="fn-backref" href="#id47">2</a>)</em> Mark L.McAuliffe, Michael J. Carey and Marvin H. Solomon. Towards
Effective and Efficient Free Space Management. ACM SIGMOD Record.
Proceedings of the 1996 ACM SIGMOD international conference on
Management of Data, June 1996.</td></tr>
</tbody>
</table>
<table class="docutils citation" frame="void" id="cockburn" rules="none">
<colgroup><col class="label" /><col /></colgroup>
<tbody valign="top">
<tr><td class="label"><a class="fn-backref" href="#id8">[COCKBURN]</a></td><td>Alistair Cockburn. Writing Effective Use Cases.</td></tr>
</tbody>
</table>
</div>
</div>
</div>
</div>


          </div>
        </div>
      </div>
      <div class="sphinxsidebar">
        <div class="sphinxsidebarwrapper">
            <h3><a href="index.html">Table Of Contents</a></h3>
            <ul>
<li><a class="reference external" href="#">SimpleDBM Developers&#8217;s Guide</a><ul>
<li><a class="reference external" href="#introduction">Introduction</a><ul>
<li><a class="reference external" href="#intended-audience">Intended Audience</a></li>
<li><a class="reference external" href="#pre-requisite-reading">Pre-requisite Reading</a></li>
</ul>
</li>
<li><a class="reference external" href="#data-manager-rss-components">Data Manager/RSS Components</a></li>
<li><a class="reference external" href="#object-registry">Object Registry</a><ul>
<li><a class="reference external" href="#overview">Overview</a></li>
<li><a class="reference external" href="#two-use-cases">Two Use cases</a></li>
<li><a class="reference external" href="#registering-an-objectfactory">Registering an ObjectFactory</a></li>
<li><a class="reference external" href="#asymmetry-between-retrieving-and-storing-objects">Asymmetry between retrieving and storing objects</a></li>
<li><a class="reference external" href="#storable-interface-and-object-serialization">Storable Interface and Object serialization</a></li>
<li><a class="reference external" href="#registering-singletons">Registering Singletons</a></li>
<li><a class="reference external" href="#historical-note">Historical Note</a></li>
<li><a class="reference external" href="#comparison-with-apache-derby">Comparison with Apache Derby</a></li>
</ul>
</li>
<li><a class="reference external" href="#storage-factory">Storage Factory</a><ul>
<li><a class="reference external" href="#id3">Overview</a></li>
<li><a class="reference external" href="#storage-containers">Storage Containers</a></li>
<li><a class="reference external" href="#storage-container-registry">Storage Container Registry</a></li>
<li><a class="reference external" href="#default-implementation">Default Implementation</a></li>
</ul>
</li>
<li><a class="reference external" href="#latch-manager">Latch Manager</a><ul>
<li><a class="reference external" href="#id4">Overview</a></li>
<li><a class="reference external" href="#latch-modes">Latch modes</a></li>
<li><a class="reference external" href="#implementation-and-performance-notes">Implementation and Performance Notes</a></li>
<li><a class="reference external" href="#obtaining-a-latch-instance">Obtaining a latch instance</a></li>
</ul>
</li>
<li><a class="reference external" href="#log-manager">Log Manager</a><ul>
<li><a class="reference external" href="#id5">Overview</a></li>
<li><a class="reference external" href="#write-ahead-log-wal-protocol">Write Ahead Log (WAL) Protocol</a></li>
<li><a class="reference external" href="#advantages-of-wal">Advantages of WAL</a></li>
<li><a class="reference external" href="#usage-notes">Usage Notes</a></li>
<li><a class="reference external" href="#simpledbm-implementation-of-the-log">SimpleDBM Implementation of the Log</a></li>
<li><a class="reference external" href="#limitations-of-current-design">Limitations of current design</a></li>
<li><a class="reference external" href="#operations">Operations</a><ul>
<li><a class="reference external" href="#creating-a-new-log-instance">Creating a new Log Instance</a></li>
<li><a class="reference external" href="#opening-a-log-instance">Opening a log instance</a></li>
<li><a class="reference external" href="#inserting-new-log-records">Inserting new log records</a></li>
<li><a class="reference external" href="#flushing-the-log">Flushing the Log</a></li>
<li><a class="reference external" href="#reading-log-records">Reading Log records</a></li>
<li><a class="reference external" href="#checkpoint-records">Checkpoint Records</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference external" href="#lock-manager">Lock Manager</a><ul>
<li><a class="reference external" href="#id6">Introduction</a></li>
<li><a class="reference external" href="#locking-basics">Locking Basics</a></li>
<li><a class="reference external" href="#two-phase-locking-and-repeatable-read-isolation-level">Two-Phase Locking and Repeatable Read Isolation Level</a></li>
<li><a class="reference external" href="#read-committed-isolation-level">Read Committed Isolation Level</a></li>
<li><a class="reference external" href="#serializable-isolation-level">Serializable Isolation Level</a></li>
<li><a class="reference external" href="#design-choices">Design choices</a></li>
<li><a class="reference external" href="#lock-modes">Lock Modes</a><ul>
<li><a class="reference external" href="#lock-compatibility-matrix">Lock Compatibility Matrix</a></li>
<li><a class="reference external" href="#lock-conversions">Lock Conversions</a></li>
</ul>
</li>
<li><a class="reference external" href="#id7">Operations</a><ul>
<li><a class="reference external" href="#obtaining-an-instance-of-lock-manager">Obtaining an instance of Lock Manager</a></li>
<li><a class="reference external" href="#lockable-objects">Lockable objects</a></li>
<li><a class="reference external" href="#lock-owners">Lock Owners</a></li>
<li><a class="reference external" href="#lock-durations">Lock Durations</a></li>
<li><a class="reference external" href="#acquiring-and-releasing-locks">Acquiring and releasing locks</a></li>
<li><a class="reference external" href="#algorithm">Algorithm</a><ul>
<li><a class="reference external" href="#a001-lock-acquire">a001 - lock acquire</a><ul>
<li><a class="reference external" href="#main-success-scenario">Main Success Scenario</a></li>
<li><a class="reference external" href="#extensions">Extensions</a></li>
</ul>
</li>
<li><a class="reference external" href="#a003-handle-new-request">a003 - handle new request</a><ul>
<li><a class="reference external" href="#id9">Main Success Scenario</a></li>
<li><a class="reference external" href="#id10">Extensions</a></li>
</ul>
</li>
<li><a class="reference external" href="#a002-handle-lock-conversion">a002 - handle lock conversion</a><ul>
<li><a class="reference external" href="#id11">Main Success Scenario</a></li>
<li><a class="reference external" href="#id12">Extensions</a></li>
</ul>
</li>
<li><a class="reference external" href="#a004-lock-wait">a004 - lock wait</a><ul>
<li><a class="reference external" href="#id13">Main Success Scenario</a></li>
<li><a class="reference external" href="#id14">Extensions</a></li>
</ul>
</li>
<li><a class="reference external" href="#b001-release-lock">b001 - release lock</a><ul>
<li><a class="reference external" href="#id15">Main Success Scenario</a></li>
<li><a class="reference external" href="#id16">Extensions</a></li>
</ul>
</li>
<li><a class="reference external" href="#b002-grant-waiters">b002 - grant waiters</a><ul>
<li><a class="reference external" href="#id17">Main Success Scenario</a></li>
<li><a class="reference external" href="#id18">Extensions</a></li>
</ul>
</li>
<li><a class="reference external" href="#b003-grant-conversion-request">b003 - grant conversion request</a><ul>
<li><a class="reference external" href="#id19">Main Success Scenario</a></li>
<li><a class="reference external" href="#id20">Extensions</a></li>
</ul>
</li>
<li><a class="reference external" href="#c001-check-request-compatible-with-granted-group">c001 - check request compatible with granted group</a><ul>
<li><a class="reference external" href="#id21">Main Success Scenario</a></li>
<li><a class="reference external" href="#id22">Extensions</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference external" href="#data-structures-of-the-lock-manager">Data Structures of the Lock Manager</a></li>
<li><a class="reference external" href="#deadlock-detector">Deadlock Detector</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference external" href="#page-manager">Page Manager</a><ul>
<li><a class="reference external" href="#overview-of-page-manager-module">Overview of Page Manager module</a></li>
<li><a class="reference external" href="#interactions-with-other-modules">Interactions with other modules</a></li>
<li><a class="reference external" href="#page-class">Page class</a><ul>
<li><a class="reference external" href="#page-size-and-implementation-of-storable-interface">Page Size and implementation of Storable interface</a></li>
<li><a class="reference external" href="#how-various-page-types-are-managed">How various Page types are managed</a></li>
<li><a class="reference external" href="#page-factory">Page Factory</a></li>
<li><a class="reference external" href="#id25">Page Manager</a></li>
<li><a class="reference external" href="#storing-and-retrieving-pages">Storing and retrieving Pages</a></li>
<li><a class="reference external" href="#checksum">Checksum</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference external" href="#buffer-manager">Buffer Manager</a><ul>
<li><a class="reference external" href="#id26">Overview</a></li>
<li><a class="reference external" href="#id27">Interactions with other modules</a></li>
<li><a class="reference external" href="#id28">Operations</a><ul>
<li><a class="reference external" href="#creating-a-buffer-manager-instance">Creating a Buffer Manager instance</a></li>
<li><a class="reference external" href="#fixing-pages-in-the-buffer-pool">Fixing Pages in the Buffer Pool</a></li>
<li><a class="reference external" href="#modifying-page-contents">Modifying page contents</a></li>
<li><a class="reference external" href="#changing-lock-modes">Changing lock modes</a></li>
<li><a class="reference external" href="#unfixing-a-page">Unfixing a Page</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference external" href="#transaction-manager">Transaction Manager</a><ul>
<li><a class="reference external" href="#id29">Introduction</a></li>
<li><a class="reference external" href="#overiew">Overiew</a></li>
<li><a class="reference external" href="#what-is-aries">What is ARIES?</a></li>
<li><a class="reference external" href="#aries-an-overview">ARIES - An Overview</a></li>
<li><a class="reference external" href="#features-of-aries">Features of ARIES</a></li>
<li><a class="reference external" href="#key-differences-from-aries">Key differences from ARIES</a></li>
<li><a class="reference external" href="#transactions-and-locks">Transactions and Locks</a></li>
<li><a class="reference external" href="#transactions-and-modules">Transactions and Modules</a></li>
<li><a class="reference external" href="#transactions-and-log-records">Transactions and Log records</a></li>
<li><a class="reference external" href="#the-loggable-hierarchy">The Loggable hierarchy</a><ul>
<li><a class="reference external" href="#loggable-hierarchy">Loggable Hierarchy</a></li>
<li><a class="reference external" href="#transaction-manager-internal-log-records">Transaction Manager Internal Log Records</a></li>
<li><a class="reference external" href="#redoable">Redoable</a></li>
<li><a class="reference external" href="#baseloggable-abstract-class">BaseLoggable abstract class</a></li>
<li><a class="reference external" href="#pageformatoperation">PageFormatOperation</a></li>
<li><a class="reference external" href="#multipageredo">MultiPageRedo</a></li>
<li><a class="reference external" href="#undoable">Undoable</a></li>
<li><a class="reference external" href="#physical-undos">Physical Undos</a></li>
<li><a class="reference external" href="#singlepagelogicalundos">SinglePageLogicalUndos</a></li>
<li><a class="reference external" href="#logicalundos">LogicalUndos</a></li>
<li><a class="reference external" href="#comments-about-implementing-undo-operations">Comments about implementing undo operations</a></li>
<li><a class="reference external" href="#compensation-records">Compensation records</a></li>
<li><a class="reference external" href="#nontransactionrelatedoperations">NonTransactionRelatedOperations</a></li>
<li><a class="reference external" href="#postcommitactions">PostCommitActions</a></li>
<li><a class="reference external" href="#containerdeleteoperations">ContainerDeleteOperations</a></li>
<li><a class="reference external" href="#containeropenoperations">ContainerOpenOperations</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference external" href="#space-manager">Space Manager</a><ul>
<li><a class="reference external" href="#id33">Introduction</a></li>
<li><a class="reference external" href="#comparison-with-storage-manager-module">Comparison with Storage Manager module</a></li>
<li><a class="reference external" href="#id34">Operations</a><ul>
<li><a class="reference external" href="#obtaining-an-instance-of-spacemgr">Obtaining an instance of SpaceMgr</a></li>
<li><a class="reference external" href="#creating-a-container">Creating a Container</a></li>
<li><a class="reference external" href="#extending-a-container">Extending a Container</a></li>
<li><a class="reference external" href="#deleting-a-container">Deleting a container</a></li>
<li><a class="reference external" href="#searching-for-free-space">Searching for free space</a></li>
<li><a class="reference external" href="#updating-space-information">Updating space information</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference external" href="#slotted-page-manager">Slotted Page Manager</a><ul>
<li><a class="reference external" href="#id35">Introduction</a></li>
<li><a class="reference external" href="#structure-of-slotted-page">Structure of Slotted Page</a></li>
<li><a class="reference external" href="#obtaining-instances-of-slotted-page">Obtaining instances of Slotted Page</a></li>
<li><a class="reference external" href="#inserting-or-updating-records">Inserting or updating records</a></li>
<li><a class="reference external" href="#deleting-records">Deleting records</a></li>
<li><a class="reference external" href="#accessing-records">Accessing records</a></li>
<li><a class="reference external" href="#miscellaneous-operations">Miscellaneous operations</a></li>
</ul>
</li>
<li><a class="reference external" href="#index-manager">Index Manager</a><ul>
<li><a class="reference external" href="#id36">Overview</a></li>
<li><a class="reference external" href="#challenges-with-b-tree-concurrency">Challenges with B-Tree Concurrency</a><ul>
<li><a class="reference external" href="#survey-of-algorithms">Survey of algorithms</a></li>
<li><a class="reference external" href="#limitations-of-lehman-and-yao-b-link-trees">Limitations of Lehman and Yao B-link Trees</a></li>
<li><a class="reference external" href="#recoverable-b-link-trees">Recoverable B-Link Trees</a></li>
<li><a class="reference external" href="#b-tree-algorithm-in-apache-derby">B-Tree algorithm in Apache Derby</a></li>
<li><a class="reference external" href="#simpledbm-b-link-tree">SimpleDBM B-link Tree</a></li>
</ul>
</li>
<li><a class="reference external" href="#structure-of-the-b-link-tree">Structure of the B-link Tree</a></li>
<li><a class="reference external" href="#structure-of-nodes">Structure of Nodes</a><ul>
<li><a class="reference external" href="#id42">Overview</a></li>
<li><a class="reference external" href="#leaf-nodes">Leaf Nodes</a></li>
<li><a class="reference external" href="#index-nodes">Index Nodes</a></li>
<li><a class="reference external" href="#limits">Limits</a></li>
</ul>
</li>
<li><a class="reference external" href="#key-differences-from-published-algorithm">Key Differences from published algorithm</a><ul>
<li><a class="reference external" href="#support-for-non-unique-indexes">Support for Non-Unique indexes</a></li>
<li><a class="reference external" href="#handling-of-storage-map">Handling of storage map</a></li>
<li><a class="reference external" href="#variable-length-keys">Variable length keys</a></li>
<li><a class="reference external" href="#page-split-operation">Page Split operation</a></li>
<li><a class="reference external" href="#merge-operation">Merge Operation</a></li>
<li><a class="reference external" href="#link-operation">Link Operation</a></li>
<li><a class="reference external" href="#unlink-operation">Unlink Operation</a></li>
<li><a class="reference external" href="#redistribute-keys-operation">Redistribute Keys Operation</a></li>
<li><a class="reference external" href="#increase-tree-height-operation">Increase Tree Height Operation</a></li>
<li><a class="reference external" href="#decrease-tree-height-operation">Decrease Tree Height Operation</a></li>
<li><a class="reference external" href="#index-scans">Index Scans</a></li>
<li><a class="reference external" href="#simplified-algorithm-for-scans">Simplified Algorithm for Scans</a></li>
<li><a class="reference external" href="#simpler-page-modification-checks">Simpler page modification checks</a></li>
<li><a class="reference external" href="#b-tree-index-is-a-secondary-structure">B-Tree index is a secondary structure</a></li>
</ul>
</li>
</ul>
</li>
<li><a class="reference external" href="#tuple-manager">Tuple Manager</a><ul>
<li><a class="reference external" href="#overview-of-tuple-manager">Overview of Tuple Manager</a></li>
<li><a class="reference external" href="#design-decisions">Design Decisions</a><ul>
<li><a class="reference external" href="#tuple-inserts">Tuple Inserts</a></li>
<li><a class="reference external" href="#tuple-segmentation">Tuple Segmentation</a></li>
<li><a class="reference external" href="#tuple-deletes">Tuple Deletes</a></li>
<li><a class="reference external" href="#tuple-updates">Tuple Updates</a></li>
<li><a class="reference external" href="#space-reclamation">Space Reclamation</a></li>
<li><a class="reference external" href="#tuple-segment-structure">Tuple Segment Structure</a></li>
<li><a class="reference external" href="#free-space-information">Free Space Information</a></li>
<li><a class="reference external" href="#latch-ordering">Latch Ordering</a></li>
<li><a class="reference external" href="#logging-of-space-map-page-updates">Logging of Space Map Page updates</a></li>
</ul>
</li>
</ul>
</li>
</ul>
</li>
</ul>

            <h4>Previous topic</h4>
            <p class="topless"><a href="usermanual.html"
                                  title="previous chapter">SimpleDBM RSS User&#8217;s Manual</a></p>
            <h3>This Page</h3>
            <ul class="this-page-menu">
              <li><a href="_sources/developerguide.txt"
                     rel="nofollow">Show Source</a></li>
            </ul>
          <div id="searchbox" style="display: none">
            <h3>Quick search</h3>
              <form class="search" action="search.html" method="get">
                <input type="text" name="q" size="18" />
                <input type="submit" value="Go" />
                <input type="hidden" name="check_keywords" value="yes" />
                <input type="hidden" name="area" value="default" />
              </form>
              <p class="searchtip" style="font-size: 90%">
              Enter search terms or a module, class or function name.
              </p>
          </div>
          <script type="text/javascript">$('#searchbox').show(0);</script>
        </div>
      </div>
      <div class="clearer"></div>
    </div>
    <div class="related">
      <h3>Navigation</h3>
      <ul>
        <li class="right" style="margin-right: 10px">
          <a href="usermanual.html" title="SimpleDBM RSS User’s Manual"
             >previous</a></li>
        <li><a href="index.html">SimpleDBM v1.0.12 BETA documentation</a> &raquo;</li> 
      </ul>
    </div>
    <div class="footer">
      &copy; Copyright 2009, Dibyendu Majumdar.
      Created using <a href="http://sphinx.pocoo.org/">Sphinx</a> 0.6.5.
    </div>
  </body>
</html>